用中序和后序遍历序列构建二叉树

用中序和后序遍历序列构建二叉树

问题

这个题目说的是，给你一棵二叉树的中序和后序遍历序列，你要根据这两个序列构建这棵二叉树。假设这棵二叉树节点上没有重复的数字。

比如说，给你的中序遍历序列和后序遍历序列分别是：

中序遍历序列：2, 1, 8, 4, 16
后序遍历序列：2, 8, 16, 4, 1

你要返回用它们构建出的二叉树，是：

    1
  /   \
 2     4
      / \
     8  16

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  private TreeNode buildTree(
    int[] post, int postStart, int postEnd,
    int inStart, Map<Integer, Integer> inPos) {

    if (postStart > postEnd) return null;
    TreeNode root = new TreeNode(post[postEnd]);
    int rootIdx = inPos.get(post[postEnd]);
    int leftLen = rootIdx - inStart;
    root.left = buildTree(post, postStart, postStart+leftLen-1, inStart, inPos);
    root.right = buildTree(post, postStart+leftLen, postEnd-1, rootIdx+1, inPos);
    return root;
  }

  // Time: O(n), Space: O(n)
  public TreeNode buildTree(int[] in, int[] post) {
    Map<Integer, Integer> inPos = new HashMap<>();
    for (int i = 0; i < in.length; ++i)
      inPos.put(in[i], i);
    return buildTree(post, 0, post.length-1, 0, inPos);
  }

}