第 8 关 | 二叉树的深度优先经典问题：3. 黄金挑战 —

1. 最近祖先问题

如果将搜索二叉树换成普通的二叉树该怎么做呢？这就是LeetCode236.给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

例如，对于下面的二叉树：

示例1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

要想找到两个节点的最近公共祖先节点，我们可以从两个节点往上找，每个节点都往上走，一直走到根节点，那么根节点到这两个节点的连线肯定有相交的地方，如果是从上往下走，那么最后一次相交的节点就是他们的最近公共祖先节点。我们就以找6和7的最近公共节点来画个图看一下：

6的祖先结点有3 和5，7的是3，5，2，所以6和7的最近公共祖先是5。如果要用代码实现，需要考虑好几种情况。根据以上定义，若 root是 p, q 的最近公共祖先，则只可能为以下情况之一：

(1)p和 q 在 root 的子树中，且分列 root 的异侧（即分别在左、右子树中）；(2)p = root，且 q 在 root 的左或右子树中；(3)q = root，且 p在 root 的左或右子树中；

而具体在执行递归时，我们要判断的情况稍微复杂一些：例如我们在上面的树中查找6和7的公共祖先，遍历的时候从树的根节点开始逐步向下，假如某个时刻访问的结点为root，我们通过后序递归的查找其左右子树，则此时的判断逻辑是：

如果left和right都为null，说明在该子树root里p和q一个都没找到，直接返回null即可。例如上图中递归到了root为1的子树时。
如果left和right都不为null，说明p和q分别在root的两侧，例如root为5时，此时6和7就分别在其两侧，直接返回5即可。
当right为空，left不为空时，此时情况略复杂，要考虑两种情况：(1)先判断一下root是不是p或者q，如果是说明q和p一个是另一个的祖先，直接返回就好了，否则：（2）说明right子树里什么都没查到，而6和7是在left子树里，此时需要递归的去左子树查即可。例如root为3时，此时递归的结果必然是right为null而left不为空。
如果left为空，而right不为空，说明是与情况3相反的情况。

总结看递归的代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p ,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left == null &&right == null){
            return null;
        }
        if(left == null){
            return right;
        }
        if(right == null){
            return left;
        }
        return root;
    }
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL || root == p || root == q) {
        return root;
    }
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left == NULL && right == NULL) {
        return NULL; // 1.
    }
    if (left == NULL) {
        return right; // 3.
    }
    if (right == NULL) {
        return left; // 4.
    }
    return root; // 2. if(left != null and right != null)
}

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 and not right: return # 1.
        if not left: return right # 3.
        if not right: return left # 4.
        return root # 2. if left and right:

第 8 关 | 二叉树的深度优先经典问题：3. 黄金挑战 —— 寻找祖先问题-灵析社区

1. 最近祖先问题