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.

 Notice

Assume two nodes are 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

思路

1. 拿到题第一个要问的是, 这两个node都一定存在于树里面吗?
2. 假设左节点返回lca, 右节点返回lca, 那么root肯定是lca
3. 什么是lca, 节点本身是它自己的lca. 所以向上遇到target的时候, 返回它本身, 否则返回null
4. 如果两个节点其中一个是另一个的父节点, 返回该父节点即可

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null) {
            return null;
        }

        if (root == A || root == B) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);

        if (left != null && right != null) {
            return root;
        }

        if (left != null) {
            return left;
        }
        if (right != null) {
            return right;
        }

        return null;
    }