No.236 二叉树的最近公共祖先 (Medium)

题目描述

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

5和1的公共祖先是3
5和4大公共祖先是5

思路

递归，设root为最近公共祖先，那么只有以下三种情况：

1. p, q分别在root的不同侧；
2. root == p, q是p的后代；
3. root == q, p是q的后代

那么我们递归的核心思路就是：

1. 传入root结点和p，q结点，如果p在root的左子树（或者右子树），q在root的右子树（或者左子树中），返回root, root就是最近公共结点。
2. p或者q如果都不在root的左子树或者右子树中，则返回null
3. p如果在root的左子树或者右子树中，但是q不在，返回p结点；
4. q如果在root的左子树或者右子树中，但是p不在，返回q结点；

PS: 该题不是很理解代码，先背下来

代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 终止条件
        // 1. root == null : 无结点了
        // 2. root == p; 传入的结点等于p结点
        // 3. root == q; 传入的结点等于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;
    }
}