105. 从前序遍历与中序遍历序列构造二叉树

发表于 | 分类于
又荒废了一段时间

耗时：40 min

105. 从前序与中序遍历序列构造二叉树

递归

前序遍历：中-左-右
中序遍历：左-中-右

因此可以先从前序遍历找到根元素，再由中序确定左右子树的个数

1
2
3
4
5
6
7
8
9
var buildTree = function(preorder, inorder) {
    if (preorder.length === 0 || inorder.length=== 0) return null
    let nodeVal = preorder.shift()
    let node = new TreeNode(nodeVal)
    let index = inorder.indexOf(nodeVal)
    node.left = buildTree(preorder.slice(0,index), inorder.slice(0,index))
    node.right = buildTree(preorder.slice(index),inorder.slice(index + 1))
    return node
};
优化

slice 是很耗性能的，其实没有必要传递数组，函数传递指针即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var buildTree = function(preorder, inorder) {
    var helper = function (p_start,p_end,i_start,i_end) {
        
        if (p_start > p_end || i_start > i_end ) return null
        let nodeVal = preorder[p_start]
        let node = new TreeNode(nodeVal)
        let index = inorder.indexOf(nodeVal)
        let left = index - i_start 
        node.left = helper(p_start + 1 , p_start + left , i_start ,index - 1)
        node.right = helper(p_start + left + 1,p_end, index + 1,i_end)
        return node
    }
    return helper(0,preorder.length - 1,0,preorder.length - 1)
};

总结：

利用 前序和中序的性质，定位根节点，求出左右子树的个数。然后递归构建左右子树即可