LeetCode 235. Lowest Common Ancestor of a Binary Search Tree
题目
思路
- 两个值都小于根节点值，则在左子树中递归找公共根节点
- 两个值都大于根节点值，则值右子树中递归找公共根节点
- 一个大于等于根节点值，一个小于等于根节点值，则公共根节点为root本身。
代码
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root == None:
return None
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
return root