Construct Binary Tree from Preorder and Postorder Traversal
MedPrompt
Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.
If there exist multiple answers, you can return any of them.
Example 1:
Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]Example 2:
Input: preorder = [1], postorder = [1]
Output: [1]
Constraints:
1 <= preorder.length <= 301 <= preorder[i] <= preorder.length- All the values of
preorderare unique. postorder.length == preorder.length1 <= postorder[i] <= postorder.length- All the values of
postorderare unique. - It is guaranteed that
preorderandpostorderare the preorder traversal and postorder traversal of the same binary tree.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the properties of preorder and postorder traversals into a recursive algorithm. It identifies the root and then determines the bounds of the left and right subtrees by finding the left child's root in the postorder array. It then creates new sub-arrays for the left and right subtrees and calls itself recursively. While conceptually straightforward, this method is highly inefficient due to the overhead of creating array slices in each step.
Algorithm
- Create a recursive function
construct(pre, post). - Base Case: If the
prearray is empty, returnnull. - Create a
TreeNodefor the root usingpre[0]. - If
prehas only one element, return the root node as it's a leaf. - Identify the root of the left subtree, which is
pre[1]. - Linearly scan the
postarray to find the index of the left subtree's root. Let this bepostIdx. - The number of nodes in the left subtree is
leftSubtreeSize = postIdx + 1. - Create new arrays (slices) for the left and right subtrees from the
preandpostarrays.- Left subtree
preorder:pre.slice(1, 1 + leftSubtreeSize) - Left subtree
postorder:post.slice(0, leftSubtreeSize) - Right subtree
preorder:pre.slice(1 + leftSubtreeSize, pre.length) - Right subtree
postorder:post.slice(leftSubtreeSize, post.length - 1)
- Left subtree
- Recursively call
constructfor the left and right subtrees and assign them toroot.leftandroot.right. - Return the
root.
Walkthrough
The fundamental idea relies on the traversal orders:
- Preorder:
Root -> Left -> Right - Postorder:
Left -> Right -> Root
From this, we know that preorder[0] is the root of the current tree. If the tree is not just a single node, preorder[1] must be the root of the left subtree. We can then find this value (preorder[1]) in the postorder array. All elements in the postorder array up to and including this value belong to the left subtree. This allows us to determine the size of the left subtree.
Once we know the size of the left subtree, we can partition both the preorder and postorder arrays into three parts: the root, the left subtree's elements, and the right subtree's elements. We then make recursive calls on these smaller, newly created sub-arrays to build the left and right children of the root.
import java.util.Arrays; /** * 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 { public TreeNode constructFromPrePost(int[] preorder, int[] postorder) { if (preorder == null || preorder.length == 0) { return null; } TreeNode root = new TreeNode(preorder[0]); if (preorder.length == 1) { return root; } int leftRootVal = preorder[1]; int leftSubtreeSize = 0; for (int i = 0; i < postorder.length; i++) { if (postorder[i] == leftRootVal) { leftSubtreeSize = i + 1; break; } } root.left = constructFromPrePost( Arrays.copyOfRange(preorder, 1, 1 + leftSubtreeSize), Arrays.copyOfRange(postorder, 0, leftSubtreeSize) ); if (preorder.length > 1 + leftSubtreeSize) { root.right = constructFromPrePost( Arrays.copyOfRange(preorder, 1 + leftSubtreeSize, preorder.length), Arrays.copyOfRange(postorder, leftSubtreeSize, postorder.length - 1) ); } return root; }}Complexity
Time
O(N^2), where N is the number of nodes. For each node, we might scan a significant portion of the `postorder` array and create new sub-arrays, both of which are O(N) operations. This leads to a quadratic time complexity.
Space
O(N^2), where N is the number of nodes. The recursion depth can be O(N), and at each level, new arrays are created, leading to a quadratic space complexity in the worst case.
Trade-offs
Pros
Easy to understand and implement.
Directly follows the definitions of the traversals.
Cons
Very inefficient in both time and space.
Creating new array slices in every recursive call leads to high memory usage and overhead.
Solutions
Solution
public class Construct_Binary_Tree_from_Preorder_and_Postorder_Traversal { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { /* preorder -> [1] [2,4,5] [3,6,7] postorder -> [4,5,2] [6,7,3] [root] */ public TreeNode constructFromPrePost ( int [] pre , int [] post ) { return helper ( pre , 0 , pre . length - 1 , post , 0 , post . length - 1 ); } // preL 和 preR 分别表示左子树区间的开头和结尾位置 // postL 和 postR 表示右子树区间的开头和结尾位置 TreeNode helper ( int [] pre , int preL , int preR , int [] post , int postL , int postR ) { if ( preL > preR || postL > postR ) { return null ; } // root node TreeNode node = new TreeNode ( pre [ preL ]); if ( preL == preR ) { // leaf node return node ; } // 找左子树的根结点(pre[preL + 1) 在 post[] 中的位置 // pre[preL + 1 here "+1" to skip above root node int idx = - 1 ; for ( idx = postL ; idx <= postR ; ++ idx ) { if ( pre [ preL + 1 ] == post [ idx ]) { break ; } } // left sub tree length: (idx - postL) // right sub tree length: node . left = helper ( pre , preL + 1 , preL + 1 + ( idx - postL ), post , postL , idx ); node . right = helper ( pre , preL + 1 + ( idx - postL ) + 1 , preR , post , idx + 1 , postR - 1 ); // postR - 1 to skip root return node ; } } } ////// class Solution { public TreeNode constructFromPrePost ( int [] pre , int [] post ) { int length = pre . length ; if ( length == 0 ) return null ; else if ( length == 1 ) return new TreeNode ( pre [ 0 ]); else { TreeNode root = new TreeNode ( pre [ 0 ]); int leftChild = pre [ 1 ]; int leftCount = 0 ; for ( int i = 0 ; i < length ; i ++) { if ( post [ i ] == leftChild ) { leftCount = i + 1 ; break ; } } root . left = constructFromPrePost ( Arrays . copyOfRange ( pre , 1 , 1 + leftCount ), Arrays . copyOfRange ( post , 0 , leftCount )); root . right = constructFromPrePost ( Arrays . copyOfRange ( pre , 1 + leftCount , length ), Arrays . copyOfRange ( post , leftCount , length - 1 )); return root ; } } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.