g***j
发帖数: 1275 | 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*****n
发帖数: 618 | 2 DFS level order traverse |
f********4
发帖数: 988 | 3 第一个时间复杂度是O（n）不？其实我周五刚面过这个题。。
就是这么做的
不过后来看到一个dfs level order travel的，这个复杂度是多少啊 |
x*********w
发帖数: 533 | 4
如果树是完全的或类似满的，先算有多少层。
然后针对每层用DFS打印，
时间复杂度因该是: n(计算深度) + n (最后一层) + n/2 (倒数第二层) + n/4 + n/8
.... 还是O(n)
【在 f********4 的大作中提到】
: 第一个时间复杂度是O（n）不？其实我周五刚面过这个题。。
: 就是这么做的
: 不过后来看到一个dfs level order travel的，这个复杂度是多少啊
|
f********4
发帖数: 988 | 5
8
恩，晓得了，多谢~
【在 x*********w 的大作中提到】
:
: 如果树是完全的或类似满的，先算有多少层。
: 然后针对每层用DFS打印，
: 时间复杂度因该是: n(计算深度) + n (最后一层) + n/2 (倒数第二层) + n/4 + n/8
: .... 还是O(n)
|
p*****2
发帖数: 21240 | 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的？
|
K**********g
发帖数: 118 | 7 是的。
对于退化成单链表的二叉树， 则是O(n^2)复杂度
8
【在 x*********w 的大作中提到】
:
: 如果树是完全的或类似满的，先算有多少层。
: 然后针对每层用DFS打印，
: 时间复杂度因该是: n(计算深度) + n (最后一层) + n/2 (倒数第二层) + n/4 + n/8
: .... 还是O(n)
|
