0106. Construct Binary Tree from Inorder and Postorder Traversal
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
Description
Given two integer arrays inorder
and postorder
where inorder
is the inorder traversal of a binary tree and postorder
is the postorder traversal of the same tree, construct and return the binary tree.
Example 1:

**Input:** inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
**Output:** [3,9,20,null,null,15,7]
Example 2:
**Input:** inorder = [-1], postorder = [-1]
**Output:** [-1]
Constraints:
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder
andpostorder
consist of unique values.Each value of
postorder
also appears ininorder
.inorder
is guaranteed to be the inorder traversal of the tree.postorder
is guaranteed to be the postorder traversal of the tree.
ac
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
// edge cases
if (postorder.length == 0 || inorder.length == 0) return null;
return helper(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
}
private TreeNode helper(int[] inorder, int istart, int iend, int[] postorder, int pstart, int pend) {
// exit
if (pstart > pend || istart > iend) return null;
if (pstart == pend || istart == iend) return new TreeNode(postorder[pstart]);
// find root index
int rootIdx = -1;
for (int i = istart; i <= iend; i++) {
if (postorder[pend] == inorder[i]){
rootIdx = i;
break;
}
}
int len = rootIdx - istart;
// divide and conquer
TreeNode root = new TreeNode(inorder[rootIdx]);
root.left = helper(inorder, istart, rootIdx-1, postorder, pstart, pstart+len-1);
root.right = helper(inorder, rootIdx+1, iend, postorder, pstart+len, pend-1);
return root;
}
}
Previous0105. Construct Binary Tree from Preorder and Inorder TraversalNext0107. Binary Tree Level Order Traversal II
Last updated
Was this helpful?