BiruLyu
8/3/2017 - 4:15 PM

## 106. Construct Binary Tree from Inorder and Postorder Traversal(#).java

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
int[] ps = new int[] {postorder.length - 1};
return helper(inorder, postorder, 0, inorder.length - 1, ps);
}

private TreeNode helper(int[] in, int[] pos, int is, int ie, int[] ps) {
if (is > ie) return null;
TreeNode root = new TreeNode(pos[ps[0]--]);
int i = 0;
for (i = ie; i >= is; i--) if (in[i] == root.val) break;
root.right = helper(in, pos, i + 1, ie, ps);
root.left = helper(in, pos, is, i - 1, ps);
return root;
}
}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private TreeNode helper(int[] inorder, int[] postorder, int rootIdx, int start, int end) {
if (rootIdx > inorder.length || start > end) return null;
TreeNode root = new TreeNode (postorder[rootIdx]);
int inIdx = 0;
for (int i = start ; i <= end; i++) {
if (inorder[i] == root.val) {
inIdx = i;
}
}
root.left = helper(inorder, postorder, rootIdx - (end - inIdx) - 1, start, inIdx - 1);
root.right = helper(inorder, postorder, rootIdx - 1, inIdx + 1, end);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
return helper(inorder, postorder,postorder.length - 1, 0, postorder.length - 1);
}
}``````