剑指offer·JS版 | 重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解法 1: 递归

首先前序/后序遍历 + 中序遍历可以重建二叉树。题目考察的就是前序+中序来重建二叉树，后序+中序的思路是类似的。

例子与思路

假设有二叉树如下：

    1   /   2   3 / 4   5

它的前序遍历的顺序是：1 2 4 5 3。中序遍历的顺序是：4 2 5 1 3

因为前序遍历的第一个元素就是当前二叉树的根节点。那么，这个值就可以将中序遍历分成 2 个部分。在以上面的例子，中序遍历就被分成了 4 2 5 和 3 两个部分。4 2 5就是左子树，3就是右子树。

最后，根据左右子树，继续递归即可。

专注前端与算法的系列干货分享，欢迎关注(¬‿¬)：
「微信公众号：心谭博客」| xxoo521.com | GitHub

代码实现

// ac地址：https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6// 原文地址：https://xxoo521.com/2019-12-21-re-construct-btree//* function TreeNode(x) {    this.val = x;    this.left = null;    this.right = null;} *//** * @param {TreeNode} pre * @param {TreeNode} vin * @return {TreeNode} */function reConstructBinaryTree(pre, vin) {    if (!pre.length || !vin.length) {        return null;    }    const rootVal = pre[0];    const node = new TreeNode(rootVal);    let i = 0; // i有两个含义，一个是根节点在中序遍历结果中的下标，另一个是当前左子树的节点个数    for (; i < vin.length; ++i) {        if (vin[i] === rootVal) {            break;        }    }    node.left = reConstructBinaryTree(pre.slice(1, i + 1), vin.slice(0, i));    node.right = reConstructBinaryTree(pre.slice(i + 1), vin.slice(i + 1));    return node;}