从前序与中序遍历序列构造二叉树

[pwstrick]

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

/**
 * 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.length == 0 || inorder.length == 0) {
        return null;
    }
    if(preorder.length == 1 && inorder.length == 1) {
        return new TreeNode(preorder[0]);
    }
    let rootVal = preorder[0];
    let root = new TreeNode(rootVal);
    let rootPos = inorder.indexOf(rootVal);             //根结点位置
    let leftInorder = inorder.slice(0, rootPos);        //左子树中序遍历
    let rightInorder = inorder.slice(rootPos + 1);      //右子树中序遍历
    let leftPreorder = preorder.slice(1, leftInorder.length + 1);       //左子树前序遍历
    let rightPreorder = preorder.slice(leftInorder.length + 1);         //右子树前序遍历
    root.left = buildTree(leftPreorder, leftInorder);       //左子树
    root.right = buildTree(rightPreorder, rightInorder);    //右子树

    return root;
    // console.log(root);
    // console.log(leftInorder, rightInorder, leftPreorder, rightPreorder);
};