东莞锂电池网站建设,网站商品台管理系统,做彩票网站违法吗,做网站建设一条龙全包【LetMeFly】235.二叉搜索树的最近公共祖先#xff1a;用搜索树性质#xff08;不遍历全部节点#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
给定一个二叉搜索树, 找到该树中两个指定节点的最近公…【LetMeFly】235.二叉搜索树的最近公共祖先用搜索树性质不遍历全部节点
力扣题目链接https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
例如给定如下二叉搜索树: root [6,2,8,0,4,7,9,null,null,3,5] 示例 1:
输入: root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。示例 2:
输入: root [6,2,8,0,4,7,9,null,null,3,5], p 2, q 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。 说明:
所有节点的值都是唯一的。p、q 为不同节点且均存在于给定的二叉搜索树中。
方法一用搜索树性质不遍历全部节点
需要注意的是这道题给定的二叉树是二叉搜索树。因此对于某个节点root
如果root.val p.val并且root.val q.val就说明p和q都在root的左子树上。令root root.left。否则如果root.val p.val并且root.val q.val就说明p和q都在root的右子树上。令root root.right。否则说明p和q在root的左右子树上或者就是rootroot即为p和q的最近公共祖先。
以上。
时间复杂度 O ( N ) O(N) O(N)其中 N N N是二叉树节点个数空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
class Solution { // AC,83.74%,90.18%
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {while (true) {if (root-val p-val root-val q-val) {root root-right;}else if (root-val p-val root-val q-val) {root root-left;}else {return root;}}}
};Python
# # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:while True:if root.val p.val and root.val q.val:root root.rightelif root.val p.val and root.val q.val:root root.leftelse:return root同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/136279915
