剑指 Offer 07. 重建二叉树

难度：中等

problem

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例1：

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例2：

Input: preorder = [-1], inorder = [-1]
Output: [-1]

solution

先序遍历第一个元素是整个二叉树的根节点，找到这个根节点。

在中序遍历中找到根节点，根节点在中序遍历中将二叉树分为了左右两边。

再在左边的二叉树中找到根节点，根据中序遍历将其分为左右两边，右边的二叉树也同理，递归。

code

/**
 * 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) return null;
    let nodeVal = preorder[0];
    let node = new TreeNode(nodeVal);
    let nodeIndexOfInorder = inorder.indexOf(nodeVal);
    let leftInorder = inorder.slice(0, nodeIndexOfInorder);
    let rightInorder = inorder.slice(nodeIndexOfInorder + 1);
    let leftPreorder = preorder.slice(1, 1 + nodeIndexOfInorder);
    let rightPreorder = preorder.slice(1 + nodeIndexOfInorder);
    
    node.left = buildTree(leftPreorder, leftInorder);
    node.right = buildTree(rightPreorder, rightInorder);
    
    return node;
};