106. Construct Binary Tree from Inorder and Postorder Traversal

Problem Statement

Pattern: Related: 105. Construct Binary Tree from Preorder and Inorder Traversal

---

Solution

int[] preOrder;
int[] postOrder;
int[] inOrder;
int index;
 
// find position of rootVal in inorder arr
int posInorder(int start, int rootVal) {
	while (inOrder[start] != rootVal)start++;
	return start;
}
 
TreeNode buildPost(int inStart, int inEnd) {
	if(index < 0 || inStart > inEnd) return null;
 
	TreeNode root = new TreeNode(postOrder[index--]);
	int pos = posInorder(inStart, root.val);
 
	root.right = buildPost(pos + 1, inEnd);
	root.left = buildPost(inStart, pos-1);
 
	return root;
}
 
TreeNode buildTree(int[] inOrderArr, int[] postOrderArr) {
	postOrder = postOrderArr;
	inOrder = inOrderArr;
	index = postOrder.length-1;
	return buildPost(0, inOrder.length-1);
}

Notes

• to understand this, understand 105. Construct Binary Tree from Preorder and Inorder Traversal