Rebuild a Tree From Its Node-First and Middle-Out Listings
Solve this ProblemYou are given two lists that describe the same binary tree with distinct values: preorder, which lists each node before its left subtree and its right subtree, and inorder, which lists the left subtree, then the node, then the right subtree. Rebuild the tree and return its root. (Two empty lists describe the empty tree.)
The first preorder value is the root, and its position in the inorder list splits the remaining values into the left and right subtrees. Doing that split with a scan at every node is slow; storing the inorder positions in a map and reading the preorder with a running index makes each step constant time.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; all values are distinct, −1000 ≤ value ≤ 1000 - ◆
preorder lists the node values as: node, then its whole left subtree, then its whole right subtree. inorder lists them as: left subtree, node, right subtree - ◆
preorder and inorder have the same length and describe the same tree (this is guaranteed) - ◆
Return the root of the tree they describe. The result is checked as a level-order list (missing children shown as null); two empty listings give the empty tree
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Find the Root in the Inorder List by Scanning, Then Split
BruteThe first value of a preorder range is its root. Find that value in the inorder range by scanning; everything to its left in the inorder range is the left subtree and everything to its right is the right subtree, so the left subtree contains exactly (index − start) nodes. Those many values immediately after the root in the preorder range are the left subtree's preorder, and the rest belong to the right subtree; rebuild each side recursively with the corresponding index ranges (no copying of arrays). The scan is a linear search at every node, so a lopsided tree costs O(n²) overall; the recursion adds O(h) space.
O(n²)O(h)1class Solution {
2 public TreeNode buildFromPreIn(int[] preorder, int[] inorder) {
3 return rebuild(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
4 }
5
6 private TreeNode rebuild(int[] pre, int ps, int pe, int[] in, int is, int ie) {
7 if (ps > pe) return null;
8 TreeNode root = new TreeNode(pre[ps]);
9 int k = is;
10 while (in[k] != pre[ps]) k++;
11 int leftSize = k - is;
12 root.left = rebuild(pre, ps + 1, ps + leftSize, in, is, k - 1);
13 root.right = rebuild(pre, ps + leftSize + 1, pe, in, k + 1, ie);
14 return root;
15 }
16}Optimal — Precompute Inorder Positions and Consume the Preorder in Order
OptimalTwo observations make each step O(1). First, look positions up in a map built once from the inorder list, instead of scanning for the root every time. Second, the preorder is consumed strictly from left to right: the next unread value is always the root of the next subtree to build (the whole left subtree comes before the right one in preorder, and recursion builds them in exactly that order). So keep a single running index into the preorder, and recurse on an inorder range [lo, hi]: if it is empty return nothing; otherwise take the next preorder value as the root, look up its inorder position mid, and build the left subtree from [lo, mid − 1] followed by the right subtree from [mid + 1, hi]. O(n) time, O(n) space for the map.
O(n)O(n)1class Solution {
2 private int next;
3
4 public TreeNode buildFromPreIn(int[] preorder, int[] inorder) {
5 Map<Integer, Integer> where = new HashMap<>();
6 for (int i = 0; i < inorder.length; i++) where.put(inorder[i], i);
7 next = 0;
8 return rebuild(preorder, where, 0, inorder.length - 1);
9 }
10
11 private TreeNode rebuild(int[] pre, Map<Integer, Integer> where, int lo, int hi) {
12 if (lo > hi) return null;
13 int value = pre[next++];
14 TreeNode root = new TreeNode(value);
15 int mid = where.get(value);
16 root.left = rebuild(pre, where, lo, mid - 1);
17 root.right = rebuild(pre, where, mid + 1, hi);
18 return root;
19 }
20}