Newsletter #187 Solution

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;
  }
}

class Solution {

  Map<Integer, Integer> inorderIdxMap;
  int postorderIdx;
  int[] postorder;

  public TreeNode buildTree(int[] inorder, int[] postorder) {
    this.postorder = postorder;

    inorderIdxMap = new HashMap<Integer, Integer>();

    for (int i = 0; i < inorder.length; i++) {
      inorderIdxMap.put(inorder[i], i);
    }

    postorderIdx = postorder.length - 1;

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

  private TreeNode buildTree(int inorderLeft, int inorderRight) {
    if (inorderLeft > inorderRight) {
      return null;
    }

    int nodeValue = postorder[postorderIdx];
    int rootIdx = inorderIdxMap.get(nodeValue);

    postorderIdx--;

    TreeNode node = new TreeNode(nodeValue);

    node.right = buildTree(rootIdx + 1, inorderRight);
    node.left = buildTree(inorderLeft, rootIdx - 1);

    return node;
  }
}