Rebuild a Tree From Its Middle-Out and Node-Last Listings
Solve this ProblemYou are given two lists that describe the same binary tree with distinct values: inorder, which lists the left subtree, then the node, then the right subtree, and postorder, which lists the left subtree, then the right subtree, then the node itself. Rebuild the tree and return its root. (Two empty lists describe the empty tree.)
The last postorder value is the root, and its position in the inorder list splits the remaining values into the left and right subtrees. A map of inorder positions makes each split constant time; reading the postorder backwards, the right subtree has to be built before the left one.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; all values are distinct, −1000 ≤ value ≤ 1000 - ◆
inorder lists the node values as: left subtree, node, right subtree. postorder lists them as: left subtree, right subtree, then the node itself - ◆
inorder and postorder 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 LAST value of a postorder range is its root (a node comes after both of its subtrees). Find that value in the inorder range by scanning; everything before it in the inorder range is the left subtree and everything after it is the right subtree. The left subtree has (index − start) nodes, so the first that many values of the postorder range are the left subtree's postorder, the next ones belong to the right subtree, and the last one is the root itself. Rebuild each side recursively with index ranges (no array copying). The linear scan at every node makes a lopsided tree cost O(n²); the recursion adds O(h) space.
O(n²)O(h)1class Solution {
2 public TreeNode buildFromInPost(int[] inorder, int[] postorder) {
3 return rebuild(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
4 }
5
6 private TreeNode rebuild(int[] in, int is, int ie, int[] post, int ps, int pe) {
7 if (ps > pe) return null;
8 TreeNode root = new TreeNode(post[pe]);
9 int k = is;
10 while (in[k] != post[pe]) k++;
11 int leftSize = k - is;
12 root.left = rebuild(in, is, k - 1, post, ps, ps + leftSize - 1);
13 root.right = rebuild(in, k + 1, ie, post, ps + leftSize, pe - 1);
14 return root;
15 }
16}Optimal — Precompute Inorder Positions and Read the Postorder Backwards
OptimalBuild a map from value to inorder position once, so a root is located in O(1). Then notice that reading the postorder from its END gives: root, then the whole RIGHT subtree (in reverse), then the whole LEFT subtree — exactly the order in which a recursion that builds the right subtree first will need them. Keep one running index starting at the last position of the postorder, and recurse on an inorder range [lo, hi]: if it is empty return nothing; otherwise take the value at the running index (moving it one step back) as the root, find its position mid, and build the RIGHT subtree from [mid + 1, hi] BEFORE the left one from [lo, mid − 1]. O(n) time, O(n) space for the map.
O(n)O(n)1class Solution {
2 private int next;
3
4 public TreeNode buildFromInPost(int[] inorder, int[] postorder) {
5 Map<Integer, Integer> where = new HashMap<>();
6 for (int i = 0; i < inorder.length; i++) where.put(inorder[i], i);
7 next = postorder.length - 1;
8 return rebuild(postorder, where, 0, inorder.length - 1);
9 }
10
11 private TreeNode rebuild(int[] post, Map<Integer, Integer> where, int lo, int hi) {
12 if (lo > hi) return null;
13 int value = post[next--];
14 TreeNode root = new TreeNode(value);
15 int mid = where.get(value);
16 root.right = rebuild(post, where, mid + 1, hi);
17 root.left = rebuild(post, where, lo, mid - 1);
18 return root;
19 }
20}