Construct Binary Tree from Inorder and Postorder
MediumArrayTreeBinary TreeSimulation
Description
Given two integer arrays inorder and postorder where inorder is the inorder traversal and postorder is the postorder traversal, construct and return the binary tree.
Examples
Input:
inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]Output:
[3,9,20,null,null,15,7]Explanation:
Reconstructed tree from traversals.
Input:
inorder = [1], postorder = [1]Output:
[1]Explanation:
Edge case with a single-element array.
Input:
inorder = [4,2,5,1,6,3], postorder = [4,5,2,6,3,1]Output:
[1,2,3,4,5,6]Explanation:
The postorder traversal tells us the root is 1 (last element). In inorder, 1 splits the array into left subtree [4,2,5] and right subtree [6,3]. Recursively applying this process: left subtree has root 2 with left child 4 and right child 5, right subtree has root 3 with left child 6. This creates a balanced binary tree.
Constraints
- •
1 ≤ inorder.length ≤ 3000 - •
postorder.length == inorder.length