106. Construct Binary Tree from Inorder and Postorder Traversal

Description

Here

Intuition

可以用recursion

第一种比第二种省一个parameter

public TreeNode buildTree(int[] inorder, int[] postorder) {
    final Map<Integer, Integer> valToIndex = new HashMap<>();
    for (int i = 0; i < postorder.length; i++) {
      valToIndex.put(postorder[i], i);
    }
    return buildTree(valToIndex, inorder, postorder, 0, postorder.length - 1, postorder.length - 1);
  }

  private static TreeNode buildTree(final Map<Integer, Integer> valToIndex, final int[] inorder,
                                    final int[] postorder, final int inStart, final int inEnd, final int postIndex) {
    if (inStart > inEnd) {
      return null;
    }
    if (inStart == inEnd) {
      return new TreeNode(inorder[inStart]);
    }
    final TreeNode root = new TreeNode(postorder[postIndex]);
    int rootIndex = valToIndex.get(postorder[postIndex]);
    root.left = buildTree(valToIndex, inorder, postorder, inStart, rootIndex - 1, postIndex - inEnd + rootIndex - 1);
    root.right = buildTree(valToIndex, inorder, postorder, rootIndex + 1, inEnd, postIndex - 1);
    return root;
  }

  public TreeNode buildTree(int[] inorder, int[] postorder) {
    final Map<Integer, Integer> valToIndex = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
      valToIndex.put(inorder[i], i);
    }

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

  private TreeNode buildTree(final Map<Integer, Integer> valToIndex, final int[] inorder, final int is, final int ie,
                             int[] postorder, int ps, int pe) {
    if (is > ie || ps > pe) {
      return null;
    }

    final int rootIndex = valToIndex.get(postorder[pe]);
    // pe 这一行满足 pe - ps = rootIndex - 1 - is, 
    final TreeNode left = buildTree(valToIndex, inorder, is, rootIndex - 1, postorder, ps, rootIndex - 1 - is + ps);
    final TreeNode right = buildTree(valToIndex, inorder, rootIndex + 1, ie, postorder, rootIndex - is + ps, pe - 1);

    final TreeNode root = new TreeNode(postorder[pe]);
    root.left = left;
    root.right = right;

    return root;
  }