【LeetCode 刷题】二叉树-公共祖先

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为二叉树公共祖先问题相关的题目解析。

文章目录

• 236. 二叉树的最近公共祖先
• 235. 二叉搜索树的最近公共祖先

236. 二叉树的最近公共祖先

题目链接

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root

• 后序遍历，最开始的判断条件为：root 为 None、p、q 时，都返回 root 本身

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

题目链接

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.right, p, q)
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        return root

• 不需要完整的后序遍历，而是根据 root 的值，可以知道正确的路径，因此只选择一个路径进行递归
• 先判断 root 比 p、q 都大和都小的情况，最后处理 root 在中间的情况，从而能够避免考虑 p.val 和 q.val 哪个大