这个题目有什么trick - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

这个题目有什么trick

这个题目有什么trick# JobHunting - 待字闺中

g*j2013-04-21 07:04

1 楼

Given a binary tree, return the bottom-up level order traversal of its nodes
' values. (ie, from left to right, level by level from leaf to root).
就是打印node level by level 但是要从最后一层开始网上打印，按照以前的思路用一
个queue，从上往下level by level打印，用一个stack把结果保存起来，然后return的
时候，挨个从stack里面pop出来。
请问有没有算法不同时用queue和stack的？

b*n2013-04-21 07:04

2 楼

DFS level order traverse

f*42013-04-21 07:04

3 楼

第一个时间复杂度是O（n）不？其实我周五刚面过这个题。。
就是这么做的
不过后来看到一个dfs level order travel的，这个复杂度是多少啊

x*w2013-04-21 07:04

4 楼

如果树是完全的或类似满的，先算有多少层。
然后针对每层用DFS打印，
时间复杂度因该是: n(计算深度) + n (最后一层) + n/2 (倒数第二层) + n/4 + n/8
.... 还是O(n)

【在 f********4 的大作中提到】

: 第一个时间复杂度是O（n）不？其实我周五刚面过这个题。。
: 就是这么做的
: 不过后来看到一个dfs level order travel的，这个复杂度是多少啊

f*42013-04-21 07:04

5 楼

8
恩，晓得了，多谢~

【在 x*********w 的大作中提到】

:
: 如果树是完全的或类似满的，先算有多少层。
: 然后针对每层用DFS打印，
: 时间复杂度因该是: n(计算深度) + n (最后一层) + n/2 (倒数第二层) + n/4 + n/8
: .... 还是O(n)

p*22013-04-21 07:04

6 楼

nodes
还不如用一个array呢。

【在 g***j 的大作中提到】

: Given a binary tree, return the bottom-up level order traversal of its nodes
: ' values. (ie, from left to right, level by level from leaf to root).
: 就是打印node level by level 但是要从最后一层开始网上打印，按照以前的思路用一
: 个queue，从上往下level by level打印，用一个stack把结果保存起来，然后return的
: 时候，挨个从stack里面pop出来。
: 请问有没有算法不同时用queue和stack的？