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  and , the LCA is .

For  and , the LCA is .

For  and , the LCA is .

 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==A || root==B) return root;

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

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

         if (lch!=null && rch!=null) return root;

         return lch==null? rch : lch;

     }

 }