JobHunting版 - Print a binary tree in level order but starting from leaf node up to root |
|---|
|
|
|
|
|
|
a*******y
发帖数: 1040 | 1 能用另外一个stack来保存结果，最后再打印，但是假如让你每个level之间print 换行
，怎么办？
这题的变化是，给你任何一个height的level，start from there to print up | l****c
发帖数: 782 | 2 新手我试一下哈
typedef struct Node{
int value;
int level;
struct Node *left;
struct Node *right;
} node;
void_print(int LEVEL)
{
node *root;
if (LEVEL==0) return;
node *tmp = root;
queue.push(tmp);
stack.push(tmp);
while (queue.front()->level < LEVEL) {
int tmp_level = queue.front()->level;
while(queue.front()->level==tmp_level) {
node *tmp = queue.pop_front();
queue.push_back(tmp->left);
queue.push_back(tmp->right);
stack.push_back(tmp->left);
stack.push_back(tmp->right);
}
}
while(!stack.isempty()) {
int tmp_level = stack.top.level;
while (stack.top.level==tmp_level) printf("%d",stack.pop_back()->value);
printf("\n");
}
} | b******g
发帖数: 77 | 3 struct Node
{
Value value;
Node * left;
Node * right;
}
void printBT(Node * root);
void printBT(vector & v1);
void printBT(Node * root)
{
vector v1;
v1.push_back(root);
printBT(v1);
}
// recursively printBT Date structure: using two vectors -- v1 holds nodes
of current level, v2 hold nodes of next level;
void printBT(vector & v1)
{
if ( v1.empty() )
return;
vector v2;
Node * node;
for (int i = 0; i < v1.size(); i++) // Push all children of v1 into v2;
{
node = v1[i];
if (node->left != NULL)
v2.push_back( node->left )
if (node->right != NULL)
v2.push_back( node->right )
}
printBT(v2); // call function PrintBT (v2), if v2 is empty, then means
no nodes at this level, just return;
for (int i = 0; i < v1.size(); i++) // print nodes at current level
{
node = v[i];
cout << node->value << " ";
}
cout << endl;
}
【在 a*******y 的大作中提到】
: 能用另外一个stack来保存结果，最后再打印，但是假如让你每个level之间print 换行
: ，怎么办？
: 这题的变化是，给你任何一个height的level，start from there to print up
| a*******y
发帖数: 1040 | | b******g
发帖数: 77 | 5 刚才有几个笔误，现在再看看吧。
【在 a*******y 的大作中提到】
: 唉，你们这都是什么啊
: 那个明白人来给说说
| Z*****Z
发帖数: 723 | 6 不错，和倒着打印链表差不多
【在 b******g 的大作中提到】
: 刚才有几个笔误，现在再看看吧。
| l****c
发帖数: 782 | 7 So, I think that another BULL GUY is using recursive to push_back the lower
layer's values into container. And when it reaches the lowest level begin
to print, then the 2nd lowest layer's values printed.
I am trying to use non-recursive means. From the highest level, push the
node into a queue (for next level) and a stack for final printing. When the
level popped out from the queue increases to the lower level, check whether
it is the objective. If yes, stop and print everything in the stack. Because
it is a LIFO, the printed result is like the lower layer printed first. If
no, continue to pop the node from the queue and push this node's leaves into
this queue and the stack... until you reach the level you need. | Z*****Z
发帖数: 723 | 8 我觉得你的思路是对的。实现上，同递归的版本比起来，有些可以改进。。。
假设树是full and complete的，一共有N个节点。那个递归的写法的空间复杂度 的大头
就是N。而你的写法，到最后，栈里面存了所有的N个节点，队列里面还有最后一层N/2
个节点，一共是3N/2，再加上你貌似给每个node还加了一个level的field。。。
lower
the
whether
Because
If
into
【在 l****c 的大作中提到】
: So, I think that another BULL GUY is using recursive to push_back the lower
: layer's values into container. And when it reaches the lowest level begin
: to print, then the 2nd lowest layer's values printed.
: I am trying to use non-recursive means. From the highest level, push the
: node into a queue (for next level) and a stack for final printing. When the
: level popped out from the queue increases to the lower level, check whether
: it is the objective. If yes, stop and print everything in the stack. Because
: it is a LIFO, the printed result is like the lower layer printed first. If
: no, continue to pop the node from the queue and push this node's leaves into
: this queue and the stack... until you reach the level you need.
| l****c
发帖数: 782 | 9 Yes, as a beginner, I still could not consider the things like complexity.
The level I could reach is to finish question...... How to improve?
In addition, the reason I added the level is that lz's asking to print the
values of levels higher than a particular one.
大头
/2
【在 Z*****Z 的大作中提到】
: 我觉得你的思路是对的。实现上，同递归的版本比起来，有些可以改进。。。
: 假设树是full and complete的，一共有N个节点。那个递归的写法的空间复杂度 的大头
: 就是N。而你的写法，到最后，栈里面存了所有的N个节点，队列里面还有最后一层N/2
: 个节点，一共是3N/2，再加上你貌似给每个node还加了一个level的field。。。
:
: lower
: the
: whether
: Because
: If
|
|
|
|
|
|
|
|
