【剑指Offer】68.2 二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 不是二叉搜索，没有了值的比较
        // 递归
        if(root == null || p == root || q == root)
            return root;


        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null) // 此时值在右子树
            return right;
        if(right == null) // 此时值在左子树
            return left;
        return root; // 分别在左右子树
    }
}