> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/amazon-mock-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/amazon-mock-interview/phone-interview-ii/88lowest-common-ancestor.md).

# 88.Lowest Common Ancestor

## 1.Description(Medium)

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.

### Notice

Assume two nodes are exist in tree.

**Example**

For the following binary tree:

```
  4
 / \
3   7
   / \
  5   6
```

LCA(3, 5) =`4`

LCA(5, 6) =`7`

LCA(6, 7) =`7`

## 2.Code

```
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        if(root==null || root==A || root==B){//当前节点为空或者是AB其中一个就返回当前节点
            return root;
        }

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

        //Conquer
        if(left!=null && right!=null){  //AB位于左右子树两侧
            return root;
        }
        if(left!=null){            //此处右子树应该为空，因为找不到A,B任何一个，AB全在左子树上
            return left;
        }
        if(right!=null){
            return right;
        }

        return null;
```