JZ4 重建二叉树

Leetcode

Publish Date: 2021-06-30

Update Date: 2021-06-30

解法

function reConstructBinaryTree(pre, vin)
{
    if(!pre.length || !vin.length){
        return null
    }

    let root = new TreeNode(pre[0])
    let index = vin.indexOf(pre[0])
    
    root.left = reConstructBinaryTree(pre.slice(1, index + 1), vin.slice(0, index))
    root.right = reConstructBinaryTree(pre.slice(index + 1), vin.slice(index + 1))
    
    return root
}

解析

了解前序遍历和中序遍历的特点后比较简单，看一下前序遍历的代码可知，pre数组内的第一个元素就是根元素。然后在中序遍历vin数组内找到该元素，根据中序遍历的特点，vin数组内pre[0]左边就是左子树的成员，pre[0]右侧就是右子树的成员。根据两侧成员数量就可以得到pre[1] -> pre[index]就是左子树的部分，pre[index + 1]到最后就是右子树的部分，于是有了下面的代码

root.left = reConstructBinaryTree(pre.slice(1, index + 1), vin.slice(0, index))
root.right = reConstructBinaryTree(pre.slice(index + 1), vin.slice(index + 1))