重建二叉树

题目描述

示例

代码

代码1 使用递归，根据前序的根，从中序中确定左右子树，然后继续分解

/*
已知前序（根左右）序列和中序（左根右）序列，可以唯一确定一棵二叉树
1. 根据前序序列第一个节点确定根节点
2. 根据根节点在中序序列中的位置分割出左右两个子序列
3. 对左子树和右子树分别递归使用同样的方法继续分解

例如：
前序序列{1,2,4,7,3,5,6,8} = pre
中序序列{4,7,2,1,5,3,8,6} = vin
1. 根据前序序列的第一个节点可知根节点为 1
2. 找到1在中序序列中的位置，为vin[3]
3. 切割左右子树，则 vin[3]的前边为左子树， in[3]的后边为右子树
4. 切割后的左子树的前序序列为{2,4,7} 切割后的左子树的中序序列为{4,7,2}
    切割后的右子树的前序序列为{3,5,6,8} 切割后的右子树的中序序列为{5,3,8,6}
5. 对子树分别使用同样的方法分解
*/
function reConstructBinaryTree(pre, vin)
{
    if(pre.length === 0 || vin.lengh ==0) return null
    
    // 前序序列的第一个节点为根节点，构造根节点
    let root = new TreeNode(pre[0])
    
    // 在中序中找到前序的根
    for(let i = 0; i < vin.length;i++){
        if(vin[i] === pre[0]){
            // 获得左子树，注意这里的区间。
            // 如果在中序序列中的 i=3 比如 (4 7 2) 1 (5 3 8 6)，说明左子树有3个节点
            // 所以在找到左子树当前对应的前序序列时 从前序序列截取出来 就是 pre.slice(1,4)也即(i+1)
            root.left = reConstructBinaryTree(pre.slice(1,i+1), vin.slice(0,i))
            // 获得右子树
            root.right = reConstructBinaryTree(pre.slice(i+1), vin.slice(i+1))
            break
        }
    }
    return root
}

时间复杂度O(n)

空间复杂度O(n)

题目来源

JZ7 重建二叉树