LEETCODE 235. 二叉搜索树的最近公共祖先
题目描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 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 为不同节点且均存在于给定的二叉搜索树中。
代码实现
class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ self.res_p = [] self.res_q = [] def find(root,arr,n,is_p): if not root: return if root and root.val==n: arr.append(root) if is_p: self.res_p = list(arr) else: self.res_q = list(arr) find(root.left,arr+[root],n,is_p) find(root.right,arr+[root],n,is_p) find(root,[],p.val,True) find(root,[],q.val,False) i = 0 j = 0 pre = root while i<len(self.res_p) and j<len(self.res_q): if self.res_p[i] != self.res_q[i]: break pre = self.res_p[i] i += 1 j += 1 return pre
更优的实现方式
class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ node = root while node: if p.val>node.val and q.val>node.val: node = node.right elif p.val<node.val and q.val<node.val: node = node.left else: return node return node1 次阅读