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