题目链接
题目描述:
根据一棵树的前序遍历与中序遍历构造二叉树。
太经典了,不需要例子了~
解题思路
还是给一个例子吧!
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
如果这是一道选择填空甚至应用题,我们会怎么做?
- 由前序遍历特点可知,根结点
root
是”排头兵”,也就是3
。 - 根据
root
值找到中序遍历数组中的相应索引,这时由中序遍历特点可知,左子树位于根结点索引左侧,也就是9
;右子树位于根结点索引右侧15,20,7
。 - 对左、右子树数组重复1、2步骤,直到数组为空
这就是我们日常做题的步骤,不难发现,其中蕴含着分治和递归的思想。分治部分可以参考二分查找算法,其实没差太多~简而言之,就是利用前序遍历得到根结点值去划分中序遍历左右子树,而后按根、左、右
顺序递归建立二叉树。下面说三个细节:
- 如何通过前序遍历的根结点值找到对应中序遍历索引?当然可以通过遍历中序数组查找到根结点值。不过,为了降低执行用时,本文采用
unordered_map
提前记录中序遍历键值对(亲自测试,从20ms降到12ms)。 - 对于划分左右子树区间以及递归结束条件的确定,参考二分查找的查找区间细节。注意本文的左右指针设置为
l = 0, r = length
,即[l...r)
左闭右开区间。 - 如何确定先序遍历中根结点位置?(为什么自增就确定是下一个根结点?)一定要结合先序遍历本身特点(根结点是”排头兵”),以及我们构建二叉树的顺序(根、左、右)。这就涉及到递归的流程(考虑栈的特点),一定是等左子树建完再去建右子树。所以这样自增是么问题哒。如果是根右左建树,显然自增不管用了,得通过中序遍历数组找右子树”排头兵”,忒麻烦了~~
代码
cpp
1 | class Solution { |
如果有错误或者不严谨的地方,请务必给予指正,十分感谢。