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

描述#

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

比如说，给你的前序遍历序列和中序遍历序列分别是：
前序遍历序列：1, 2, 4, 8, 16
中序遍历序列：2, 1, 8, 4, 16
你要返回用它们构建出的二叉树，是：
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[] pre, int preStart, int preEnd,
    int inStart, Map<Integer, Integer> inPos) {

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

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

}