2021-02-09 236. 二叉树的最近公共祖先

题目地址

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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
 
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

思路

1. 最关键的是p，q一定在树中，否则这个题解并不适用（两个节点一个在某一子树中并不代表另一个节点也在，需要在看下）。

递归的确理解起来有点麻烦，由一个终止条件做界限，从一个状态切换到另一个状态，再将底层的状态结果作为上层状态的继续下去的动力，从而结束上层状态。从开始递归，不断把中间状态压栈，到达界限后不断出栈，最终返回结果。

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/9 6:21 下午
 */
public class LowestCommonAncestor {
    public static void main(String[] args) {
        int[] arr = {3,5,1,6,2,0,8,-1,-1,7,4};
        NodeTree root = NodeTree.createTree(arr);
        NodeTree first = root.getLeft();
        NodeTree second = root.getLeft().getRight();
        NodeTree ancestor = lowestCommonAncestor(root, first, second);
        if (ancestor == null) {
            System.out.println("null");
        } else {
            System.out.println(ancestor.getValue());
        }
    }

    private static NodeTree lowestCommonAncestor(NodeTree root, NodeTree first, NodeTree second) {
        //到叶子结点或者找到节点返回
        if (root == null || root == first || root == second) {
            return root;
        }
        //// 因为是先递归再判断left和right的，因此left和right如果不为null，就一定是最接近指定的两个节点的。////
        // 在左子树中找两个节点的最近公共祖先
        NodeTree left = lowestCommonAncestor(root.getLeft(), first, second);
        // 在右子树中找两个节点的最近公共祖先
        NodeTree right = lowestCommonAncestor(root.getRight(), first, second);

        // 分别在左右子树找到两个节点，返回这个根节点
        if (left != null && right != null) {
            return root;
            //至少两个节点有一个在left子树上，递归返回后如果第一层递归右子树没有，
            //那说明这个left就是两个节点的最近公共祖先
        } else if (left != null) {
            return left;
            // 至少两个节点有一个在right子树上，递归返回后如果第一层递归左子树没有，
            //那说明这个right就是两个节点的最近公共祖先
        } else if (right != null) {
            return right;
        }

        // 因为p，q一定存在这棵树中，其实这里不会走到
        return null;
    }
}