剑指 Offer.68.II-二叉树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 判断当前是否达到终止条件，root越过叶子节点，或者搜索到p或者q的节点
        if(root == null || root == p || root == q) return root;
        // 递归向左子树搜索
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 递归向右子树搜索
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 两棵子树中都不包含p或者q 证明当前两个节点没有存在树中
        if(left == null && right == null) return null; // 1.
        // 如果left为空 证明其中一个节点存在于右子树中 返回右子树的节点
        if(left == null) return right; // 3.
        // 若right为空，则证明其中一个节点存在于左子树中，返回左子树节点
        if(right == null) return left; // 4.
        // 如果左右子树都不空 则root为当前的最近祖先，返回root
        return root; // 2. if(left != null and right != null)
    }
}