236. 二叉树的最近公共祖先

https://leetcode.cn/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, 10^5] 内。
• -10^9 <= Node.val <= 10^9
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

注意所有node的值都不相同，且p和q都存在于二叉树中。

DFS-归并

如果当前节点的值与val1或val2相等，说明找到了公共祖先，否则在左右子树中寻找。

如果左右子树的返回值都非空，说明在当前节点的两侧各找到一个目标节点，此时当前节点就是最近公共祖先。

如果左右子树的返回值中有一个为空，则返回非空的返回值，根据递归函数的定义，这个返回值就是最近公共祖先。

class Solution {
    // 返回这棵树中p和q的LCA，如果p和q都在这棵树中，返回它们的LCA；如果只有一个p或q，则返回p或q；如果p和q都不在这棵树中，返回null。
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果当前节点为空，则返回null，如果为p或q，则直接返回p或q，无需继续搜索。
        if (root == null || root.val == p.val || root.val == q.val) return root;

        // 在左子树中查找p和q。注意找到p或q就返回，因为下面要么有q要么没q，有q的话LCA就是p，
        // 没q的话q肯定在另外一棵树中，我们需要返回一个非空值来声明我们找到了p，不妨就把这个返回值设为p。
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 在右子树中查找p和q
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 如果p和q分别在当前节点的左右子树中，那么当前节点就是它们的LCA
        if (left != null && right != null) {
            return root;
        }

        // 如果左子树找到了p或q，而右子树找不到，那么LCA在左子树
        // 如果右子树找到了p或q，而左子树找不到，那么LCA在右子树
        return left != null ? left : right;
    }
}

• 时间复杂度：$O(N)$，其中 $N$ 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此总的时间复杂度为 $O(N)$。
• 空间复杂度：$O(h)$，其中 $h$ 是二叉树的高度。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 $N$，因此空间复杂度为 $O(N)$。