Java LeetCode 236. 二叉树的最近公共祖先（递归）

题目描述

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

百度百科中最近公共祖先的定义为：“对于有根树 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 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3

输入：root = [1,2], p = 1, q = 2 输出：1

方法名称

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

}

题目理解

二叉树的题目天生适合使用递归来做，但是有的同学很容易被绕进去，同时，写递归代码的时候，是在凭感觉在写代码，总感觉就差那么一点儿。 这道题本人将使用本人理解的方式去画图，让整个递归过程简单明了。

本题要求的是二叉树的最近公共祖先，我们先来分析一下这个公共祖先有哪些可能。

大致的情况有这些。我们以第三种情况来说明递归的过程。

写递归的时候，要明确一点是先要操作还是先要递归。这里的操作指的是对这个结点操作比如对结点的判断，修改等；递归到了叶子结点（递归结束的条件）后要直接返回去还是操作后再回去。

画图的过程如下：

代码本身不难，难的是不理解整个的递归过程。要明白是先要操作还是先要递归。返回的过程中要不要进行操作。像本题，本题是在左递归之前，先对结点进行了判断，所以是要先操作在递归。返回的时候不需要进行操作的。 然后在继续右递归。最后，两个递归的结果用于判断是不是祖先。

题目代码

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (p == root || 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 left;
        } else if (right != null) {
            return right;
        }
        return null;
    }