题目描述

解题思路

复习二叉树的前序遍历和中序遍历

分析

我们知道，二叉树的前序遍历是先遍历根，再遍历左右子树，因此第一个节点就是根节点。我们的子问题可以变成如何重建一棵树。我们只需要如下建立一颗新的二叉树：

let node = new TreeNode(root);
node.left = ...
node.right = ...
复制代码

既然前序遍历知道根节点的索引，那么根据索引可以拿到这个根节点的值，我们就可以在后序遍历中找到这个根节点，根据中序遍历的定义，即先左子树，然后根、后右子树，我们就可以知道后序遍历中这个根的索引，根据这个索引，我们可以算出前序遍历中左子树的个数，如此，新的二叉树的左右节点就可以递归算出来了。

let node = new TreeNode(root);
node.left = (前序遍历数组，前序遍历左子树的开始位置，前序遍历左子树的结束位置，中序遍历数组， 中序遍历左子树的开始位置，中序遍历的左子树结束位置)
node.right = (前序遍历数组，前序遍历右子树的开始位置，前序遍历右子树的结束位置，中序遍历数组， 中序遍历右子树的开始位置，中序遍历右子树的结束位置)
复制代码

接下来，递归重建这颗二叉树。

步骤拆解

递归建二叉树，需要一个辅助函数，传入不同的起始和终止位置

var build = function(preorder, preStart, preEnd, inorder, inStart, inEnd){
    //
}
var buildTree = function(preorder, inorder){
    return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1)
}
复制代码

根据前序遍历取得根节点，并根据根节点，在中序遍历中找到根节点，拿到它的索引 index。以此计算中序遍历中的左右子树的起始位置。

var build = function(preorder, preStart, preEnd, inorder, inStart, inEnd){
    let root = preorder[preStart];
    let index = 0;
    for(let i = 0; i <= inEnd; i++){
        if(inorder[i] === root){
            index = i;
            break;
        }
    }
}
复制代码

因此可以得出构建 node.left 的时候，起始位置 preStart 第一轮为 0，结束位置为 index - 1，即根节点的前一个节点位置。node.right 的起始位置为 index + 1, 结束位置为 inEnd

var build = function(preorder, preStart, preEnd, inorder, inStart, inEnd){
    // ...
    let node = new TreeNode(root);
    node.left = (preorder, 未知， 未知, inorder, inStart, index - 1);
    node.right = (preorder, 未知，未知，inorder, index + 1, inEnd);
}
复制代码

计算出左子树的个数 leftSize, 以此来确定前序遍历中的左子树的起始位置。
```
let leftSize = index - inStart;
复制代码
```
因此，可以确定前序遍历的起始位置。前序遍历的第一个节点是根节点，到 leftSzie 为止时，都需要把根节点的位置算进去。因此，前序遍历的左子树的开始位置 preStart + 1，结束位置为 preStart + leftSize。前序遍历的右子树的开始位置为 preStart + leftSize + 1, 结束位置为 preEnd。
```
var build = function(preorder, preStart, preEnd, inorder, inStart, inEnd){
    // ...
    let node = new TreeNode(root);
    node.left = (preorder, preStart + 1， preStart + leftSize, inorder...);
    node.right = (preorder, preStart + leftSize + 1，preEnd，inorder...);
}
复制代码
```

最后，需要明确递归的终止条件

if(preStart > preEnd) return null;
复制代码

完整代码

/**
 * 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 build = function(preorder, preStart, preEnd, inorder, inStart, inEnd){
    if(preStart > preEnd) return null;

    let root  = preorder[preStart];
    let index = 0;

    for(let i = inStart; i <= inEnd; i++){
        if(inorder[i] === root){
            index = i;
            break;
        }
    }

    let leftSize = index - inStart;

    let node = new TreeNode(root)
    node.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
    node.right = build(preorder, preStart + leftSize + 1, preEnd,  inorder, index + 1, inEnd);
    
    return node;
}

var buildTree = function(preorder, inorder) {
    return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length -1)
};
复制代码