Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Example

For the following binary tree:

4
 / \
3   7
   / \
  5   6

LCA(3, 5) =4

LCA(5, 6) =7

LCA(6, 7) =7

1. 暴力思路是找到第一个Node的path, 找到第二个Node的Path, 然后compare
2. 一遍traversal用到divide and conquer, 如果当前节点是第一个或第二个其中一个，那么当前节点就是LCA, 如果都不是，就继续左右子树递归，如果都在左边（right is null) 那么LCA在左边，如果都在右边（ left is null) 那么LCA 在右边,如果一边一个，那么当前节点就是LCA

public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param A and B: two nodes in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        if (root == null) {
            return null;
        }


        if (root.val == A.val || root.val == B.val) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);

        if (left == null || right == null) {
            return left == null ? right : left;
        }
        return root;


    }
}