Lowest Common Ancestor of a Binary Tree II

找LCA.

这个题看了半天和I的区别, 发现只是没有要求p和q一定在树里. check一下就可以了.

/**
 * 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) {
        boolean l = check(root, p);
        boolean k = check(root, q);
        if(!l || !k)
            return null;
        return find(root, p, q);
    }
    private boolean check(TreeNode root, TreeNode p) {
        if(root == null)
            return false;
        if(root == p)
            return true;
        return check(root.left, p) || check(root.right, p);
    }
    
    private TreeNode find(TreeNode root, TreeNode p, TreeNode q) {
      if (root == null || root == p || root == q)
        // found p or q or touch the ground
        return root;

      // search p and q from left and right
      TreeNode left = find(root.left, p, q);
      TreeNode right = find(root.right, p, q);

      if (left != null && right != null)
        // from root's left & right we found both p and q, so root is the LCA
        return root;
      else
        // left is not null means from left's left & right we found both q and q
        // so left is the LCA, otherwise, right is the answer
        return left != null ? left : right;
    }
}