Problem

Given the root of a binary tree and an array of TreeNode objects nodes, return the lowest common ancestor (LCA) of all the nodes in nodes. All the nodes will exist in the tree, and all values of the tree’s nodes are unique.

Definition

Lowest Common Ancestor Definition

Examples

Consider the tree:

1
2
3
4
5
6
7

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2_     0        8
         /   \
         7    4

Example 1

1
2
3

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7]
Output: 2
Explanation: The lowest common ancestor of nodes 4 and 7 is node 2.

Example 2

1
2
3

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [1]
Output: 1
Explanation: The lowest common ancestor of a single node is the node itself.

Example 3

1
2
3

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [7,6,2,4]
Output: 5
Explanation: The lowest common ancestor of the nodes 7, 6, 2, and 4 is node 5.

Example 4

1
2
3

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [0,1,2,3,4,5,6,7,8]
Output: 3
Explanation: The lowest common ancestor of all the nodes is the root node.

Solution

This code is very similar to Lowest Common Ancestor of a Binary Tree, but we now have array instead of nodes p and q.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
	Set<TreeNode> set = new HashSet<TreeNode>(nodes);
	return dfs(root, set);
}

public TreeNode dfs(TreeNode root, Set<TreeNode> set) {
    if(root == null || set.contains(root))  {
	    return root;
	}
	TreeNode left = lowestCommonAncestor(root.left, set);
	TreeNode right = lowestCommonAncestor(root.right, set);
	if (left != null && right != null) {
		return root;
	}
	return left != null ? left : right;
}