> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/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/nine-chapter/2.binary-tree/578.lowest-common-ancestor-iii.md).

# 578.Lowest Common Ancestor III

## **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.Return

`null`if LCA does not exist.  (this is what diff with Leetcode 236)

node A or node B may not exist in tree. Each node has a different value

**Example1**

For the following binary tree:

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

LCA(3, 5) =`4`

LCA(5, 6) =`7`

LCA(6, 7) =`7`

**Example2**

```
Input: 
{4, 3, 7, #, #, 5, 6}
3 5
5 6
6 7 
5 8
Output: 
4
7
7
null
Explanation:
  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
LCA(5, 8) = null
```

**Example3**

```
Input:
{1}
1 1
Output: 
1
Explanation:
The tree is just a node, whose value is 1.
```

## 2.Code

<https://www.jiuzhang.com/problem/lowest-common-ancestor-iii/>

Solution 1: 加一个helper class 来track节点A和B是否存在

```
    private class HelperType{
        public TreeNode node;
        public boolean a_exist,b_exist;
        public HelperType(TreeNode n,boolean a,boolean b){
            a_exist=a;
            b_exist=b;
            node=n;
        }
    }

    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        HelperType result=helper(root,A,B);
        if(result.a_exist && result.b_exist){
            return result.node;
        }
        else{
            return null;
        }
    }

    public HelperType helper(TreeNode root,TreeNode A,TreeNode B){
        if(root==null){
            return new HelperType(null,false,false);
        }

        HelperType left=helper(root.left,A,B);
        HelperType right=helper(root.right,A,B);

        //use root==A/B to judge whether there exist node
        boolean aexist=left.a_exist || right.a_exist || root==A;
        boolean bexist=left.b_exist || right.b_exist || root==B;

        //LCAI and LCAII are combined with root==null
        if(root==A || root==B){
            return new HelperType(root,aexist,bexist);
        }
        //caution: left.node not left
        if(left.node!=null && right.node!=null){
            return new HelperType(root,aexist,bexist);
        }
        if(left.node!=null){
            return new HelperType(left.node,aexist,bexist);
        }
        if(right.node!=null){
            return new HelperType(right.node,aexist,bexist);
        }
        return new HelperType(null,aexist,bexist);

    }
```

Solution 2:

Divide & Conquer + Global Variable（不需要 ResultType）

这题和 LCA 原题的区别主要是要找的 A 和 B 可能并不存在树里。所以我们要做出这两个改变

1. 用全局变量把 A 和 B 是否找到保存起来。最后在 main function 里面要查看是否都找到
2. 当 root 等于 A 或者 B 时不能直接返回root了。原题可以直接返回是因为两个 node 是保证存在的所以这情况下 LCA 一定是 root。
3. 现在 root 等于 A 或者 B 我们还是要继续往下找是否存在另外的一个

不用 ResultType 的一个好处是：如果面试的时候出了一个原题，然后问这题做 follow up。如果从头开始写 result type 代码改动会比较大。一是比较容易写错，二是时间可能会不够。

这个方法只需要增加两个全局变量并且改动 LCA 原题的代码两行即可。

```
public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
    TreeNode res = divConq(root, A, B);
    if (foundA && foundB)		// 程序执行完之后查看是否两个都找到
        return res;
    else
        return null;
}

private boolean foundA = false, foundB = false;
private TreeNode divConq(TreeNode root, TreeNode A, TreeNode B) {
    if (root == null)
        return root;
    
    TreeNode left = divConq(root.left, A, B);
    TreeNode right = divConq(root.right, A, B);
    
    // 如果 root 是要找的，更新全局变量 
    //（！！注意这里一定要在divide之后，这是和原题LCA不同的地方,236这里可在前可在后)
    if (root == A || root == B) {
        foundA = (root == A) || foundA;
        foundB = (root == B) || foundB;
        return root;
    }
    
    // 和 LCA 原题的思路一样
    if (left != null && right != null)
        return root;
    else if (left != null)	// 注意这种情况返回的时候是不保证两个都有找到的。可以是只找到一个或者两个都找到
        return left;		// 所以在最后上面要查看是不是两个都找到了
    else if (right != null)
        return right;
    return null;
}
```