4.重建二叉树

题目描述

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

思路

前序遍历： 根左右；

中序遍历： 左根右；

后序遍历： 左右根；

根据中序 + 前 / 后序遍历即可重建树，如果只有前序和后序遍历序列则重建的树有多种。

此题思路：根据前序遍历的特点，每棵子树的第一个节点为根节点，然后在中序遍历中找到根的index即可确定左右子树，将上面的步骤递归即可重建树；

代码

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 

function reConstructBinaryTree(pre, vin)
{
    if (pre.length == 0 || vin.length == 0) {
        return null;
    }
    
    // 找到根所在的index，将树分割成左右两棵子树
    let index = vin.indexOf(pre[0]);
    
    return {
        val: pre[0],
        // 左子树、右子树分别递归
        left: reConstructBinaryTree(pre.slice(1, index + 1), vin.slice(0, index)),
        right: reConstructBinaryTree(pre.slice(index + 1), vin.slice(index + 1))
    }
}