二叉搜索树的最近公共祖先

Leetcode Link: 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 - 力扣（LeetCode） 235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

题目

解法一：DFS+二叉搜索树的性质

思路： 本题需要利用好二叉搜索树的性质

• 如果 root 的值在 p 和 q 之间，则 root 一定是最近的公共祖先
• 如果 root 比 q 和 p 都大，则需要到左子树中去找
• 如果 root 比 q 和 p 都小，则需要到右子树中去找
• 如果root等于其中一个值，则公共祖先一定是root，因为在二叉搜索树中，dfs的顺序一定会先找到大的那个，则小的那个一定在下面。 题解：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        elif root.val < max(p.val, q.val) and root.val > min(p.val, q.val):
            return root
        elif root.val == p.val or root.val == q.val:
            return root

启发和联系

同类问题二叉树的最近公共祖先