Merge BSTs to Create Single BST LeetCode solution in Java

1
class Solution {
2
  public TreeNode canMerge(List<TreeNode> trees) {
3
    // Map root value to tree
4
    HashMap<Integer, TreeNode> map = new HashMap<>();
5
    for (TreeNode t : trees) {
6
      map.put(t.val, t);
7
    }
8

9
    // Merge trees
10
    for (TreeNode t : trees) {
11
      if (map.containsKey(t.val)) {
12
        merger(t, map);
13
      }
14
    }
15

16
    // After merging we should have only one tree left else return null
17
    if (map.size() != 1) return null;
18
    else {
19
      // Return the one tree left after merging
20
      for (int c : map.keySet()) {
21
        // Check if final tree is valid else return null
22
        if (isValidBST(map.get(c))) {
23
          return map.get(c);
24
        } else return null;
25
      }
26
    }
27

28
    return null;
29
  }
30

31
  void merger(TreeNode t, HashMap<Integer, TreeNode> map) {
32
    map.remove(
33
        t.val); // Remove current tree to prevent cyclical merging For. 2->3(Right) and 3->2(Left)
34
    // Merge on left
35
    if (t.left != null && map.containsKey(t.left.val)) {
36
      // Before merging child node, merge the grandchild nodes
37
      merger(map.get(t.left.val), map);
38
      t.left = map.get(t.left.val);
39
      map.remove(t.left.val);
40
    }
41

42
    // Merge on right
43
    if (t.right != null && map.containsKey(t.right.val)) {
44
      // Before merging child node, merge the grandchild nodes
45
      merger(map.get(t.right.val), map);
46
      t.right = map.get(t.right.val);
47
      map.remove(t.right.val);
48
    }
49
    // Add tree back to map once right and left merge is complete
50
    map.put(t.val, t);
51
  }
52

53
  // Validate BST
54
  public boolean isValidBST(TreeNode root) {
55
    return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
56
  }
57

58
  public boolean helper(TreeNode root, long min, long max) {
59
    if (root == null) return true;
60
    if (root.val <= min || root.val >= max) return false;
61
    return helper(root.left, min, root.val) && helper(root.right, root.val, max);
62
  }
63
}