二叉树的最近公共祖先

1.题目

这道题是2024-2-9的签到题，题目难度为中等。

考察的知识点为DFS算法。

题目链接：二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

2.思路

选择哪种算法？

对于树的问题，我们首先想到的肯定是BFS或者DFS算法，然后再根据题目的要求来选择合适的算法。很显然这道题和递归也有一定的关系，因此我们选择使用DFS算法。

解题思路是啥？

有了解题方法，我们也需要明白递归的一大特性：终止条件。如果没有终止条件，那么这个递归就相当于死循环无法结束，最终超过递归深度。根据这题的要求，我们可以得到以下几种情况（终止条件）：

• 当前结点为空
• 当前结点为根节点

接着我们还需要考虑p、q的两种情况：

• p和q在同一颗子树上
• p和q不在同一颗子树上

针对这两种情况，我们可以得到以下结论，如果p和q是在同一棵树上的时候，那么它们的最近公共祖先肯定是这颗子树的根节点；如果p和q不在同一颗树上的时候，那么它们的最近公共祖先肯定是这两颗子树的根节点的父母结点。

3.代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 如果当前树的根节点是 p 或者 q 或者为空，则返回root
        if root in (None,p,q):
            return root

        # 判断p和q是否在同一颗子树上
        # 先判断左子树
        left = self.lowestCommonAncestor(root.left,p,q)
        # 再判断右子树
        right = self.lowestCommonAncestor(root.right,p,q)

        # 如果两颗子树上面都有这两个结果，说明p和q不在同一颗子树上，则返回这两颗子树的根节点的父母结点
        if left and right:
            return root
        # 反之说明p和q在同一颗子树上，那么这颗子树的根节点就是最终结果，因此返回两颗子树中有结果的那一个
        else:
            return left or right