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

解题的关键在于要知道前序和中序的区别，
前序是根左右，中序是左根右
比如题目中给到的
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
可以知道根节点是3，然后可以从中序数组中得出左子树和右子树，分别是[9] 和 [15,20,7]
同样，知道左右子树之后，根据其数组长度，可以在前序数组中定位前序的左右子树，分别是[9] 和 [20,15,7]，这时候就要用到递归了，直到得到结果
递归的终止条件是，序列为空，返回null
序列只有一个元素(也就是叶子节点)，创造新的node，并直接返回，详见代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if(!preorder || preorder.length < 1){
        return null;
    }
    let root = preorder[0];
    let treeNode = new TreeNode(root);
    if(preorder.length === 1) {
        return treeNode;
    }
    
    let rootIndex = inorder.indexOf(root);
    let inLeftTree = inorder.slice(0, rootIndex);
    let preLeftTree= preorder.slice(1, inLeftTree.length + 1);
    let inRightTree = inorder.slice(rootIndex + 1, inorder.length);
    let preRightTree = preorder.slice(preLeftTree.length + 1, preorder.length);
    
    treeNode.left = buildTree(preLeftTree, inLeftTree);
    treeNode.right = buildTree(preRightTree, inRightTree);
    
    return treeNode;
};