荣誉版主
- 积分
- -2403
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2010-5-4
- 最后登录
- 1970-1-1
|
你之前有一篇POST提到可以有兄弟指针?
是的话,做2次DFS,第一次找到最大深度。
第二次的时候当找到深度与最大深度相同的节点的时候,利用兄弟指针把那层的兄弟节点都打光,然后
递归实现的话很自然就能返回上一层,再把上一层的的都打了,一直返回打到最顶层。
danielgao 发表于 2011-4-24 12:57 ![]()
恩,是个办法,做logn次遍历不用而外空间。
有个解法是做一个数组a[m], m是树的高度,做一次遍历,遍历过程中统计高度,a[0]上存储第一层的首节点和当前遍历到的节点(更节点), a[1]存储第二层的首节点和当前遍历到的节点,没遍历到一层的新的节点就在对应数组当前节点上add tail。最后链接数组张的各个子链。
纠正一下,这题因该是sibling节点的拉链问题,不是层次打印,我搞错了,不过问题也差不多了。 |
|