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)
};

总结:

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