578.Lowest Common Ancestor III

https://www.lintcode.com/problem/578/

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

nullif 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;
}