leetcode-105.png

构造树

这一题就要了解前序、中序的性质了
前序开头的就是根节点，中序的根节点分开了左右子树

示意图.png

从上面可以看出，3是2根节点，9是左子树，剩下的蓝色框就是右子树了
那么我们递归来进行这个过程就好了

找到根节点在中序遍历里面的index，那么就可以得出，左子树的遍历过程

root.left = 递归(preoder[1, index+1], inorder[0, index])
root.right = 递归(preoder[index+1], inorder[index+1])

var buildTree = function (preorder, inorder) {
    // 递归出口
    if (preorder.length === 0 || inorder.length === 0) return null

    let node = preorder[0]
    let indexRoot = inorder.indexOf(node)

    let root = new TreeNode(node)
    root.left = buildTree(preorder.slice(1, indexRoot + 1), inorder.slice(0, indexRoot))
    root.right = buildTree(preorder.slice(indexRoot + 1), inorder.slice(indexRoot + 1))
    return root
};