首页 > 代码库 > leetcode 235. Lowest Common Ancestor of a Binary Search Tree
leetcode 235. Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______6______ / ___2__ ___8__ / \ / 0 _4 7 9 / 3 5
For example, the lowest common ancestor (LCA) of nodes 2
and 8
is 6
. Another example is LCA of nodes 2
and 4
is 2
, since a node can be a descendant of itself according to the LCA definition.
通过观察可以发现,如果p和q分别位于root的两侧,那么root就是他们的LCA。否则的话,判断一下LCA应该是在左边还是在右边。注意L11 L13的return不能缺,因为这里并不是在调用这个函数,而是在递归定义。
1 def lowestCommonAncestor(self, root, p, q): 2 """ 3 :type root: TreeNode 4 :type p: TreeNode 5 :type q: TreeNode 6 :rtype: TreeNode 7 """ 8 if (p.val <= root.val and q.val >= root.val) or (p.val >= root.val and q.val <= root.val): 9 return root 10 elif p.val < root.val: 11 return self.lowestCommonAncestor(root.left, p, q) 12 else: 13 return self.lowestCommonAncestor(root.right, p, q)
leetcode 235. Lowest Common Ancestor of a Binary Search Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。