# Construct Binary Tree from Inorder and Postorder Traversal

LintCode-72.Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Notice: You may assume that duplicates do not exist in the tree.

Given inorder [1,2,3] and postorder [1,3,2], return a tree:

``````  2
/ \
1   3
``````
``````/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/

public class Solution {
/**
*@param inorder : A list of integers that inorder traversal of a tree
*@param postorder : A list of integers that postorder traversal of a tree
*@return : Root of a tree
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || inorder.length == 0 ||
postorder == null || postorder.length == 0) {
return null;
}

return buildTree(inorder, 0, inorder.length - 1,
postorder, 0, postorder.length - 1);
}

private TreeNode buildTree(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return null;
}

int rootVal = postorder[postEnd];
int rootIndex = 0;

for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}

int len = rootIndex - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = buildTree(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + len - 1);
root.right = buildTree(inorder, rootIndex + 1, inEnd, postorder, postStart + len, postEnd - 1);

return root;
}
}
``````

Hope this helps,
Michael