Problem
Given two integer arrays preorder and postorder, where preorder represents the preorder traversal and postorder represents the postorder traversal of the same binary tree, construct and return the binary tree.If multiple binary trees can produce the same traversals, you may return any of them.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
preorder = [1,2,4,5,3,6,7]
postorder = [4,5,2,6,7,3,1] Output
root = [1,2,3,4,5,6,7]
1
/ \
2 3
/ \ / \
4 5 6 7
Solution
This solution uses recursion to construct the tree from the preorder and postorder traversals. The first element of every preorder range is always the root of that subtree.After creating the root, the next element in the preorder array represents the root of the left subtree. We use its position in the postorder array to determine how many nodes belong to the left subtree.
Once the left subtree size is known, the preorder and postorder ranges can be divided into the left and right subtrees. The same process is applied recursively until all nodes are constructed.
class Solution {
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
return buildTree(preorder, postorder, 0, preorder.length - 1,
0, postorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int[] postorder,
int preStart, int preEnd, int postStart, int postEnd) {
if (preStart > preEnd)
return null;
TreeNode root = new TreeNode(preorder[preStart]);
if (preStart == preEnd)
return root;
int leftSubtreeLength = 0;
for (int i = postStart; i <= postEnd; i++) {
leftSubtreeLength++;
if (postorder[i] == preorder[preStart + 1])
break;
}
root.left = buildTree(preorder, postorder,
preStart + 1,
preStart + leftSubtreeLength,
postStart,
postStart + leftSubtreeLength - 1);
root.right = buildTree(preorder, postorder,
preStart + leftSubtreeLength + 1,
preEnd,
postStart + leftSubtreeLength,
postEnd - 1);
return root;
}
}
Complexity
Each node is processed once, and the HashMap provides constant-time access to positions in the postorder array. Therefore, the overall time complexity isO(n).
The HashMap requires
O(n) space, and the recursive call stack can grow up to O(n) in the worst case.