题目描述

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

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

样例

例如，给出

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

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

算法分析

如图所示，[pl,pr]和[il,ir]分别以前序和中序的方式维护一棵树，前序遍历的第一个元素则是当前树的根结点的值x，找到x值在中序遍历的位置y，可知[pl + 1,pl + len]和[il,y - 1]维护的是同一棵左子树，[pl + len + 1,pr]和[y + 1,ir]维护的是同一颗右子树

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    static Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    static TreeNode build(int[] preorder, int[] inorder, int pl, int pr, int il, int ir)
    {
        if(pl > pr || il > ir) return null;
        int x = preorder[pl];
        int y = map.get(x);
        int len = y - il;
        TreeNode root = new TreeNode(x);
        root.left = build(preorder, inorder, pl + 1,pl + len, il, y - 1);
        root.right = build(preorder, inorder, pl + len + 1, pr, y + 1, ir);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map.clear();
        int n = preorder.length;
        for(int i = 0;i < n;i ++)
        {
            map.put(inorder[i], i);
        }

        return build(preorder,inorder,0,n - 1,0,n - 1);
    }
}