> For the complete documentation index, see [llms.txt](https://shuati.gitbook.io/crack-lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shuati.gitbook.io/crack-lintcode/binary-tree/lowest-common-ancestor-iii-1.md).

# Lowest Common Ancestor III

 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.\
Return `null` if LCA does not exist.

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param root: The root of the binary tree.
     * @param A: A TreeNode
     * @param B: A TreeNode
     * @return: Return the LCA of the two nodes.
     */
     
    public boolean foundA = false, foundB = false;
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        TreeNode res = helper(root,A,B);
        
        if(foundA && foundB){
            return res;
        }else{
            return null;
        }
        
    }
   
    public TreeNode helper(TreeNode root, TreeNode A, TreeNode B){
        if(root == null){
            return root;
        }
        
        //先分派 再检查 不然结果会出错
        TreeNode left = helper(root.left,A,B);
        TreeNode right = helper(root.right,A,B);
        if(root == A|| root == B){
            //如果不或foundA， 当找到A后 遍历别的点时，如果root != //A，将会改变foundA的值
        
            foundA = (root == A )|| foundA; 
            foundB = (root == B) ||foundB;
            
            return root;
        }
        

        
        if(left != null && right != null){
            return root;
        }
        
        else if(left != null){
            return left;
        }
        else if(right != null){
            return right;
        }
        
        return null;
    }
    
    
}
```