LeetCode学习笔记——二叉树的最近公共祖先

阅读数：22次

2020-05-19

最近有一道题频繁让我遇到，就是求二叉树的最近公共祖先，其实很好理解，就是求两个结点的最近相交的结点

遇到树的问题，大多数情况都要往递归方向思考，那确定了递归做法，就得考虑怎么递，又怎么归，今天，借助这道题，总结一下递归的常规做法。

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

比如给定一个二叉树，求结点 8 和结点 5 的公共祖先，可知 公共祖先 为结点3，也是根节点。

当我们在思考如何递归的时候，不要那么贪心的想要把整个过程都想的明明白白，而是化整为零，先思考一个过程，再思考递推到下一个过程。

那一个过程是什么？

就是一个根节点带着两个子节点。

我们分析题目，知道给定的两个结点 p, q 不一定是分别分布在根节点的左右子树中，也可能都分布在根节点的左子树，或者都分布在根节点的右子树。

所以，我们应该一边一边的去寻找，对于单单一个过程中，先去找左子树，然后再去找右子树。

对于结点 3 这个过程：

TreeNode left = root.left;
TreeNode right = root.right;

如果没有找到，这时候就要递推了，同样的，把它的左子树和右子树分别看作根节点，各自看作一个过程继续去找，

对于结点 4 这个过程，

TreeNode left = root.left;
TreeNode right = root.right;

发现，当再以结点 4 的左右子树分别作为一个子过程的时候，结点 8 为根节点的过程是满足了题目要求，也就是根节点是满足了我们要找的结点，这时候就要返回。

if(root == p || root == q)
    return root;

而结点 8 作为结点 4 的子过程，又是结点 4 的右子树，所以返回上一层时，将是这样：

TreeNode left = root.left;
TreeNode right = 结点 8;

对于结点 4 的左子树，它啥也没找到，毫无疑问返回的是 null，

TreeNode left = null;
TreeNode right = 结点 8;

这时候，要继续往上面回归了，结点 4 往上面回归，要对结点 4 的左右子树进行判断，刚刚我们得出，在结点 4 的右子树找到了结点了，而左子树没有找到，所以要将右子树继续回归。

if(left == null)
	return right;
if(right == null)
	return left;

所以对于结点 3 这个过程，结点 4 作为它的左子树是带着结果回来了：

TreeNode left = 结点 4(结点 8);
TreeNode right = root.right;

所以对于结点 3 作为根节点来说，它的左子树这时就完成了递推和回归，而且左子树是带着结点回来的，

我们继续看结点 3 的右子树，

同样的，根据前面的步骤，会递推到 结点 6 这个位置，把结点 6 看作单独一个过程，

TreeNode left = root.left;
TreeNode right = root.right;

发现，当以结点 6 的右子树为根节点的过程是找到了结点，所以返回结点 5，而左子树啥也没，就返回null，

TreeNode left = null;
TreeNode right = 结点 5;

同样，根据前面的步骤，结点 6 继续回归，最终回归到 结点 7，

对于结点 7来说，

TreeNode left = 结点 6(结点 5);
TreeNode right = null;

这时候再看最上面的结点 3，它的右子树也回归了，也是带着值的，

对其左右子树进行判断，

if(left != null && right != null)
	return root;

对于左右子树都不为空，也是都找到值回来的，那么此根节点也就是他们最近的公共祖先。

所以，这道题总结递推和回归的情况就是，

递推

• 当以此为根节点的过程没有返回值的时候，将其左右子树再分别看作单个过程，往下递推

回归

• 当以此为根节点的过程找到了所需要的结点，返回此根节点
• 当单个过程的根节点为空的情况，就直接返回

所以综上，应该就可以对这道题的递归过程了解透了，

下面看一下完整代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //单个过程的根节点为空，则直接返回
        if(root == null)
            return root;
        //如果该过程的根节点等于需要的节点，就返回根节点
        if(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 root;
        //如果左子树找不到，说明右子树找到了，就返回右子树
        else if(left == null) {
            return right;
        }
        //如果右子树找不到，说明左子树找到了，就返回左子树
        else {
            return left;
        }

}
}

面对递归问题，我们不能急于去了解全盘的递推和回归，而是把它分成了一个一个小小单独的过程，对于单个过程来分析在什么情况进行递推，在什么情况下回归就容易许多，然后再推往整体，看看哪一部分是在递推后需要进行判断的，哪一部分是在回归时候需要判断的，这样子，这一道题就解答出来了。