106. Construct Binary Tree from Inorder and Postorder Traversal
Previous105. Construct Binary Tree from Preorder and Inorder TraversalNext107. Binary Tree Level Order Traversal II
Last updated
Last updated
// 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;
}
}/**
* Time complexity : O(N)
* Space complexity : O(N)
*/
class Solution {
private int postorderIndex = 0;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postorderIndex = postorder.length-1;
return buildTree(inorder, postorder, 0, postorderIndex);
}
private TreeNode buildTree(int[] in, int[] post, int start, int end) {
if(start > end) return null;
TreeNode node = new TreeNode(post[postorderIndex--]);
if(start == end) return node;
int rootIndex = findRootIndex(in, start, end, node.val);
node.right = buildTree(in, post, rootIndex+1, end);
node.left = buildTree(in, post, start, rootIndex-1);
return node;
}
private int findRootIndex(int[] in, int start, int end, int val) {
while(start <= end) {
if(in[start] == val) break;
start++;
}
return start;
}
}