Problem

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

思路(divide & conquer)

1. 因为A和B有可能不存在与树中, 所以需要判断是否找到他们
2. 如果都找到他们的话, 由于divide & conquer是自下而上的.
   1. 所以往上的过程中, 如果A和B都找到了, 那么lca可能是root
      1. 为什么是可能? 因为第一次找到他们两个的时候, lca毋庸置疑是root, 再向上传递的时候, lca就不应该是当前层的root了, 而是下一层的lca
   2. 如果左子问题的lca 不为空, 那么lca = left.lca
   3. 如果右子问题的lca不为空, 那么lca = right.lca

    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        return helper(root, A, B).lca;
    }

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

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

        boolean foundA = left.foundA || right.foundA || root == A;
        boolean foundB = left.foundB || right.foundB || root == B;
        TreeNode lca = (foundA && foundB) ? root : null;
        lca = left.lca != null ? left.lca : lca;
        lca = right.lca != null ? right.lca : lca;

        return new Result(foundA, foundB, lca);
    }

    class Result {
        boolean foundA;
        boolean foundB;
        TreeNode lca;

        public Result(boolean foundA, boolean foundB, TreeNode lca) {
            this.foundA = foundA;
            this.foundB = foundB;
            this.lca = lca;
        }
    }

// version 2
    private int exitsCount = 0;
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        TreeNode res = helper(root, A, B);
        if (exitsCount == 2) return res;
        return null;
    }
    private TreeNode helper(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null) return null;

        TreeNode lLca = helper(root.left, A, B);
        TreeNode rLca = helper(root.right, A, B);

        if (root == A) {
            exitsCount++;
            return A;
        }
        if (root == B) {
            exitsCount++;
            return B;
        }

        if (lLca != null && rLca != null) {
            return root;
        } 
        if (lLca != null) {
            return lLca;
        }
        if (rLca != null) {
            return rLca;
        }

        return null;
    }