83-在⼆叉树中找到两个节点的最近公共祖先

题⽬描述

给定⼀棵⼆叉树(保证⾮空)以及这棵树上的两个节点对应的val 值 o1 和 o2 ，请找到 o1 和 o2
的最近公共祖先节点。

注：本题保证⼆叉树中每个节点的val值均不相同。

如当输⼊[3,5,1,6,2,0,8,#,#,7,4] , 5 , 1 时，⼆叉树{3,5,1,6,2,0,8,#,#,7,4} 如下图所示：

所以节点值为5 和节点值为1 的节点的最近公共祖先节点的节点值为3 ，所以对应的输出为3 。节点本身可以视为⾃⼰的祖先

示例 1
输⼊: [3,5,1,6,2,0,8,#,#,7,4],5,1
输出: 3

示例 2
输⼊: {}
输出: true

思路及解答

在普通⼆叉树查找节点的最近公共祖先，我们不能直接判断出它在左⼦树，还是在右⼦树。不如暴⼒点，先在左⼦树中找，如果右⼦树没找到，
说明都在左⼦树，如果左⼦树没找到，说明都在右⼦树，如果两个在左右⼦树中分别存在，说明当前节点就是他们的⽗节点。

public class Solution86 {
    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        TreeNode result = commonAncestor(root, p, q);
        return result == null ? -1 : result.val;
    }
    public TreeNode commonAncestor(TreeNode root, int p, int q) {
        if (null == root) {
            return null;
        }
        if (root.val == p || root.val == q) {
            return root;
        }
        TreeNode left = commonAncestor(root.left, p, q);
        TreeNode right = commonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return root;
        }
    }
}

• 时间复杂度： O（n） ， n 是⼆叉树节点的个数，最坏情况下每个节点访问⼀遍
• 空间复杂度： O（n） ，递归取决于栈的深度，最差情况下，⼆叉树退化成链表，栈的深度是n