Given K nodes in a binary tree, find their lowest common ancestor.

Assumptions

• K >= 2

• There isnoparent pointer for the nodes in the binary tree

• The given K nodes areguaranteedto be in the binary tree

Examples

    5

  /   \

 9     12

/ \

2 3 14

The lowest common ancestor of 2, 3, 14 is 5

The lowest common ancestor of 2, 3, 9 is 9

Solution:

base case : root == null || root == one of the nodes时返回root

对root.left, root.right进行recursion，都不null时返回root，否则返回非空的

  public TreeNode lowestCommonAncestor(TreeNode root, List<TreeNode> nodes) {
    if (root == null) {
      return root;
    }
    for (TreeNode node : nodes) { //或者recursion前先把nodes加进set，这样不用每次loop through
      if (node == root) {
        return root;
      }
    }
    TreeNode left = lowestCommonAncestor(root.left, nodes);
    TreeNode right = lowestCommonAncestor(root.right, nodes);
    if (left != null && right != null) {
      return root;
    }
    return left == null ? right : left;
  }