剑指 Offer 07. 重建二叉树

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例：

例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：
在这里插入图片描述

思路：

二叉树前序遍历第一个点为根节点，中序遍历顺序为先左子树然后根节点最后右子树。所以先通过前序遍历找出根节点，然后将中序遍历分为左右子树两组，最后对于每个子树依次递归调用。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
var buildTree = function(preorder, inorder) {
    if(preorder.length==0 || inorder.length==0) return null;
    var index=inorder.indexOf(preorder[0]);
    var left=inorder.slice(0,index);//中序左子树
    var right=inorder.slice(index+1);//中序右子树
    return {
        val:preorder[0],
        //递归左右子树的前序，中序 
        left:buildTree(preorder.slice(1,index+1),left),
        right:buildTree(preorder.slice(index+1),right)
     }; 
};