题目描述

不用map存数据 感觉会更快一点，map遍历了一遍。在递归里面也是遍历了一遍inorder；但是少了map的存和取的步骤。提升有限。

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

  public TreeNode buildTree(int[] preorder, int[] inorder) {

  if (preorder.length!=inorder.length)
            return null;
        return build(0,preorder.length-1,preorder,
                0,preorder.length-1,inorder);

    }

    private TreeNode build(int prleft, int prright, int[] preorder, int inleft,
                           int inright, int[] inorder) {
        if (prleft>prright)
            return null;
        TreeNode node = new TreeNode(preorder[prleft]);
        int i=inleft;
        for (; i <inright+1; i++) {
            if (node.val==inorder[i])
                break;
        }
        node.left=build(prleft+1,prleft+i-inleft,preorder,inleft,i-1,inorder);
        node.right=build(prleft+i-inleft+1,prright,preorder,i+1,inright,inorder);
        return node;
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla