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.

Solution:

This question is similar to Lowest Common Ancestor with some differences.

• When LCA does not exist, return null
• When one node is a parent of the other node, return the parent node

To address these problems, we need to create a ResultType which contains LCA node and two boolean variables that indicate the avaliability of node A and B. Following four cases we have to deal with:

1. A == root || B == root
2. left subtree contains one node && right subtree contains one node
3. only left subtree contains one node
4. only right subtree contains one node

Code:

class ResultType {
    TreeNode node;
    boolean a;
    boolean b;
    public ResultType(TreeNode inNode, boolean inA, boolean inB) {
        node = inNode;
        a = inA;
        b = inB;
    }
}

public class Solution {

    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        ResultType r = helper(root, A, B);
        if (r.a && r.b) {
            return r.node;
        }
        return null;
    }

    private ResultType helper(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null) {
            return new ResultType(null, false, false);
        }
        ResultType left = helper(root.left, A, B);
        ResultType right = helper(root.right, A, B);
        boolean aExist = left.a || right.a || root == A;
        boolean bExist = left.b || right.b || root == B;
        if (root == A || root == B) {
            return new ResultType(root, aExist, bExist);
        }
        if (left.node != null && right.node != null) {
            return new ResultType(root, aExist, bExist);
        }
        if (left.node != null) {
            return new ResultType(left.node, aExist, bExist);
        }
        if (right.node != null) {
            return new ResultType(right.node, aExist, bExist);
        }
        return new ResultType(null, false, false);
    }
}