力扣---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
 

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

初步思路是：先找到从根结点分别到 p 和 q 的路径。

然后对比两者，分开的位置，即是两者的最近公共祖先。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 存储 p 的路径
        List<TreeNode> list1 = new ArrayList<>();
        // 存储 q 的路径
        List<TreeNode> list2 = new ArrayList<>();
        // 寻找 p 的路径
        dfs(root, p.val, list1);
        // 寻找 q 的路径
        dfs(root, q.val, list2);
        int len = Math.min(list1.size(), list2.size());
        for (int i = 0; i < len; i++) {
            if (list1.get(i) != list2.get(i)) {
                return list1.get(i - 1);
            }
        }
        // 题目保证有答案，不用去判断不存在答案时的情况。
        return list1.get(len - 1);
    }
    private boolean dfs (TreeNode root, int find, List<TreeNode> list) {
        list.add(root);
        if (root == null) {
            list.remove(list.size() - 1);
            return false;
        }
        if (root.val == find) {
            return true;
        }
        
        boolean ju1 = dfs(root.left, find, list);
        if (ju1) {
            return true;
        }
        boolean ju2 = dfs(root.right, find, list);
        if (ju2) {
            return true;
        }
        list.remove(list.size() - 1);
        return false;
    }
}

 优化优化：

可以想到，某个节点是最近公共祖先时，共有四种情况：

1. p 在该节点的左子树，q 在该节点的右子树。

2. q 在该节点的右子树，p 在该节点的左子树。

3. p 是节点本身，q 在该节点的子树中。

4. q 是节点本身，p 在该节点的子树中。

其中，1，2 两种情况可以合并讨论，3，4 两种情况可以合并讨论。

针对 1, 2 两种情况：可以想到，当该节点的左子树和右子树都不为空时，即是该种情况。

针对 2, 3 两种情况：可以想到，当除该节点外的其他子树不包含 p，q 任意一个，即是 3,4 情况。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode 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;
    }
}