Construct Binary Tree from Preorder and Inorder Traversal
Rebuild a binary tree from its preorder and inorder traversals. Values are distinct and the traversals describe the same tree.
Work through the cases
3 examplesInput notation
Preorder values on line 1; inorder values on line 2.Expected result
Level-order values with null for missing children and no trailing nulls.Case 1
Input
3 9 20 15 7 9 3 15 20 7
Expected output
3 9 20 null null 15 7
Case 2
Input
1 2 2 1
Expected output
1 2
Case 3
Input
7 7
Expected output
7
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Preorder gives the root order; inorder splits each root into left and right subtrees. Scanning inorder for the root every time can cost O(n^2); n ≤ 3000 is tight. Values are unique, so we map each inorder value to its index once. The first value of the current preorder slice is the root; everything left of it in inorder is the left subtree, the rest the right. Those lengths fix the next two recursive slices.
The first node preorder[0] in the pre-order sequence is the root node. We find the position k of the root node in the in-order sequence, which can divide the in-order sequence into the left subtree inorder[0..k] and the right subtree inorder[k+1..].
Through the intervals of the left and right subtrees, we can calculate the number of nodes in the left and right subtrees, assumed to be a and b. Then in the pre-order nodes, the a nodes after the root node are the left subtree, and the b nodes after that are the right subtree.
Therefore, we design a function dfs(i, j, n), where i and j represent the starting positions of the pre-order sequence and the in-order sequence, respectively, and n represents the number of nodes. The return value of the function is the binary tree constructed with preorder[i..i+n-1] as the pre-order sequence and inorder[j..j+n-1] as the in-order sequence.
The execution process of the function dfs(i, j, n) is as follows:
- If n ≤ 0, it means there are no nodes, return a null node. - Take out the first node v = preorder[i] of the pre-order sequence as the root node, and then use the hash table d to find the position k of the root node in the in-order sequence. Then the number of nodes in the left subtree is k - j, and the number of nodes in the right subtree is n - k + j - 1. - Recursively construct the left subtree l = dfs(i + 1, j, k - j) and the right subtree r = dfs(i + 1 + k - j, k + 1, n - k + j - 1). - Finally, return the binary tree with v as the root node and l and r as the left and right subtrees, respectively.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int[] preorder;
private Map<Integer, Integer> d = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
this.preorder = preorder;
for (int i = 0; i < n; ++i) {
d.put(inorder[i], i);
}
return dfs(0, 0, n);
}
private TreeNode dfs(int i, int j, int n) {
if (n <= 0) {
return null;
}
int v = preorder[i];
int k = d.get(v);
TreeNode l = dfs(i + 1, j, k - j);
TreeNode r = dfs(i + 1 + k - j, k + 1, n - 1 - (k - j));
return new TreeNode(v, l, r);
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.