二叉树的最近公共祖先_易懂清晰解法

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

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

这是一棵二叉树，先来分析几个作为最近公共祖先的特点

对于和这两个节点来说，他们的最近公共祖先明显是根节点
接下来：

我么先看一下，如果“3”是“6”和“4”的公共祖先是没问题的，但是很显然它不是最近公共祖先，那么有一个特点是“6”和“4”都处于“3”的左子树上
很显然“6”和“4”这两个节点最近公共祖先是“5”，并且分布在“5”的左右子树。

第二种情况，因为题干说明：（一个节点也可以是它自己的祖先），所以节点“5”是“5”和“2”的最近公共祖先，同样根节点”3“也是他俩的公共祖先但是不是最近公共祖先，特点也是”5“和”2“都处于”3“的左子树。

同上！到这里我们看出了最近公共祖先的特点，即：
两个节点分别位于最近公共祖先的左右子树或者有一个节点是自己和另外一个节点的公共祖先。

代码层面我们可以这样考虑：

把要找公共祖先的两个节点定义为 p 节点和 q 节点，我们找公共祖先的过程为：从根节点出发对二叉树进行遍历，在这里我采用后序遍历的方法。
当走到某一个节点时把这个节点作为根，从自身开始然后向下在子树里找 p 和 q ，看是否能够同时找到并且记录两个节点分别出现的位置。

这里我们引入三种返回值（p和q在当前根节点中出现的位置情况）
① 左树中出现 / ② 右树中出现 / ③ 根节点本身
返回值 0：p和q没有在该节点中出现
返回值 1：p和q只有一个节点出现 或者 p和q同时在一个位置出现
（都出现在左树或都出现在右树，是公共祖先但不是最近的）
返回值 2：p和q在上述三个位置的两个位置出现了（找到了~）

到这里接下来就是代码描述了，这里我用的是Java语言：

/**
 * 找二叉树的最近公共祖先
 **/
public class Solution{
    TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        // 从根节点出发进行后序遍历，找到lca(p和q出现在三个位置的两个)
        find(root,p,q);
        return lca;
    }
    // 在以root为根节点的二叉树中，是否能同时找到p和q
    private boolean find(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        int left = find(root.left,p,q) ? 1 : 0;
        int right = find(root.right,p,q) ? 1 : 0;
        int mid = (root == p || root == q) ? 1 : 0;
        if (left + right + mid == 2) {
            lca = root;
            return true;
        }
        return (left + right + mid) > 0;
    }
}

欢迎交流~