[LintCode] 578 Lowest Common Ancestor III 解题报告

Description
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.

Notice
node A or node B may not 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


思路
这题要注意A和B不一定都在子树里。
用一个ResultType来记录A和B是否在子树里存在，以及LCA node。
用分治法。
1：如果A或B在root上，那么LCA就在root上。
2：如果左子树和右子树都有LCA，那么也说明当前LCA在root上。
3：如果只有左边有LCA，那么LCA就在左边。
4：如果只有右边有LCA，那么LCA就在右边。
最后递归结束以后，需要判断是否A和B都存在。


Code

/**
 * 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 and B two nodes
     * @return: Return the LCA of the two nodes.
     */
    class ResultType {
        boolean a_exist, b_exist;
        TreeNode node;
        public ResultType (boolean a_exist, boolean b_exist, TreeNode node) {
            this.a_exist = a_exist;
            this.b_exist = b_exist;
            this.node = node;
        }
    }
    
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        
        ResultType result = helper(root, A, B);
        if (result.a_exist && result.b_exist) {
            return result.node;
        }
        return null;
    }
    
    public ResultType helper(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null) {
            return new ResultType(false, false, null);
        }
        
        ResultType left = helper(root.left, A, B);
        ResultType right = helper(root.right, A, B);
        
        boolean a_exist = left.a_exist || right.a_exist || A == root;
        boolean b_exist = left.b_exist || right.b_exist || B == root;
        
        if (A == root || B == root) {
            return new ResultType(a_exist, b_exist, root);
        }
        
        if (left.node != null && right.node != null) {
            return new ResultType(a_exist, b_exist, root);
        }
        
        if (left.node != null) {
            return new ResultType(a_exist, b_exist, left.node);
        }
        
        if (right.node != null) {
            return new ResultType(a_exist, b_exist, right.node);
        }
        
        return new ResultType(a_exist, b_exist, null);
    }
}