耗时:40 min
105. 从前序与中序遍历序列构造二叉树
递归
前序遍历:中-左-右
中序遍历:左-中-右
因此可以先从前序遍历找到根元素,再由中序确定左右子树的个数
1 | var buildTree = function(preorder, inorder) { |
优化
slice 是很耗性能的,其实没有必要传递数组,函数传递指针即可
1 | var buildTree = function(preorder, inorder) { |
总结:
利用 前序和中序的性质,定位根节点,求出左右子树的个数。然后递归构建左右子树即可