从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

  3
 / \
9  20
  /  \
 15   7

在数据结构课程中我们学过通过前序遍历序列和中序遍历序列构造二叉树的方法：

1. 从先序遍历序列中拿出一个结点 x 。
2. 建立根结点，在中序遍历序列中找出结点 x 的位置，确定以结点 x 为根结点的左右子树结点数。
3. 重复步骤 1 和步骤 2 递归建立结点 x 的左右子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //使用一个 HashMap 存储中序遍历结点的下标，在寻找结点下标时只用常数时间。
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int N = preorder.length;
        indexMap = new HashMap<>();
		//建立 HashMap
        for(int i = 0; i < N; ++i){
            indexMap.put(inorder[i], i);
        }
		//递归建立二叉树
        return buildTree(preorder, inorder, 0, N - 1, 0, N - 1);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){
        if(preorder_left > preorder_right){
            return null;
        }
		//确定二叉树根结点（先序遍历最左结点）
        int preorder_root = preorder_left;
        //找到根结点在中序遍历序列中的下标
        int inorder_root = indexMap.get(preorder[preorder_root]);
		//建立根结点
        TreeNode root = new TreeNode(preorder[preorder_root]);
		//确定根结点左子树结点的个数
        int leftSubTreeSize = inorder_root - inorder_left;
		//递归建立左子树
        root.left = buildTree(preorder, inorder, preorder_left + 1, preorder_left + leftSubTreeSize, inorder_left, inorder_root - 1);
		//递归建立右子树
        root.right = buildTree(preorder, inorder, preorder_left + leftSubTreeSize + 1, preorder_right, inorder_root + 1, inorder_right);

        return root;
    }
}

时间复杂度 O(n)，空间复杂度O(n)。