Given the postorder traversal sequence of a binary search tree, reconstruct the original tree.

Assumptions

• The given sequence is not null
• There are no duplicate keys in the binary search tree

Examples

postorder traversal = {1, 4, 3, 11, 8, 5}

the corresponding binary search tree is

    5

  /    \

3        8

/ \

1 4 11

Solution: 把数组递增排序后，就是inorder traversal

  public TreeNode reconstruct(int[] post) {
    if (post.length == 0) {
      return null;
    }
    int[] in = Arrays.copyOf(post, post.length);
    Arrays.sort(in);
    Map<Integer, Integer> hashmap = new HashMap<>();
    for (int i = 0; i < in.length; i++) {
      hashmap.put(in[i], i);
    }
    return build(in, 0, in.length - 1, post, 0, post.length - 1, hashmap);
  }
  private TreeNode build(int[] in, int instart, int inend, int[] post, int poststart, int postend, Map<Integer, Integer> hashmap) {
    if (instart > inend) {
      return null;
    }
    TreeNode root = new TreeNode(post[postend]);
    // int position = find(inorder, instart, inend, post[postend]);  利用hashmap快速找position
    int position = hashmap.get(post[postend]);
    root.left = build(in, instart, position - 1, post, poststart, poststart + position - instart - 1, hashmap);
    root.right = build(in, position + 1, inend, post, poststart + position - instart, postend - 1, hashmap);
    return root;
  }