889. Construct Binary Tree from Preorder and Postorder Traversal - Explanation
Description
You are given the preorder and postorder traversals of the same binary tree. Its node values are distinct. Reconstruct a tree that produces both traversals and return its root.
Preorder visits a node, then its left subtree, then its right subtree. Postorder visits the left subtree, then the right subtree, then the node.
The traversals may allow more than one tree, especially when a node has only one child. Return any tree consistent with both arrays. Example outputs use level-order traversal, with null for missing children and trailing nulls omitted.
Example 1:
Input: preorder = [2,1,3]
postorder = [1,3,2]
Output: [2,1,3]Explanation: Root 2 has left child 1 and right child 3. Visiting the root first gives [2,1,3]; visiting it after both children gives [1,3,2].
Example 2:
Input: preorder = [1,2,3]
postorder = [3,2,1]
Output: [1,2,null,3]Explanation: One valid answer is a left-only chain 1 → 2 → 3. A right-only chain with the same values would also produce both traversals and would be accepted.
Example 3:
Input: preorder = [3,1,2,4]
postorder = [2,1,4,3]
Output: [3,1,4,2]Explanation: Root 3 has left child 1 and right child 4. Node 1 has child 2. Preorder visits 3,1,2,4; postorder visits 2,1,4,3. The single child 2 could instead be placed on the right of 1.
Constraints:
1 <= preorder.length <= 30postorder.length == preorder.length- Each array contains every integer from
1to its length exactly once. - The arrays are valid preorder and postorder traversals of the same binary tree.
Sign in to join the discussion