劍指offer之先序非遞歸打印二叉樹(shù)
1 問(wèn)題
先序非遞歸打印二叉樹(shù)
比如二叉樹(shù)如下
* 2
* 3 5
* 1 4 2 3
* 3 2 1 5 1 4 2 3
先序原則:中左右打印節(jié)點(diǎn),如果左邊有節(jié)點(diǎn)繼續(xù)要打做節(jié)點(diǎn),打印會(huì)是如下結(jié)果
2
3
1
3
2
4
1
5
5
2
1
4
3
2
3
2 分析
我們可以用stack,先進(jìn)后出,我們先push頭結(jié)點(diǎn),然后再push它的右節(jié)點(diǎn)和左節(jié)點(diǎn),依次類(lèi)推
3 代碼實(shí)現(xiàn)
#include <iostream>
#include <stack>
using namespace std;
typedef struct Node
{
int value;
struct Node* left;
struct Node* right;
} Node;
void start_print(Node *head)
{
if (head == NULL)
{
std::cout << "head is NULL" << std::endl;
return;
}
std::stack<Node *> stack;
stack.push(head);
while (stack.size())
{
Node *node = stack.top();
std::cout << node->value << std::endl;
//do not remember pop node
stack.pop();
if (node->right)
{
stack.push(node->right);
}
if (node->left)
{
stack.push(node->left);
}
}
}
int main()
{
/* 2
* 3 5
* 1 4 2 3
* 3 2 1 5 1 4 2 3
*/
Node head1, node1, node2, node3, node4, node5, node6;
Node node7, node8, node9, node10, node11, node12, node13, node14;
head1.value = 2;
node1.value = 3;
node2.value = 5;
node3.value = 1;
node4.value = 4;
node5.value = 2;
node6.value = 3;
node7.value = 3;
node8.value = 2;
node9.value = 1;
node10.value = 5;
node11.value = 1;
node12.value = 4;
node13.value = 2;
node14.value = 3;
head1.left = &node1;
head1.right = &node2;
node1.left = &node3;
node1.right = &node4;
node2.left = &node5;
node2.right = &node6;
node3.left = &node7;
node3.right = &node8;
node4.left = &node9;
node4.right = &node10;
node5.left = &node11;
node5.right = &node12;
node6.left = &node13;
node6.right = &node14;
node7.left = NULL;
node7.right = NULL;
node8.left = NULL;
node8.right = NULL;
node9.left = NULL;
node9.right = NULL;
node10.left = NULL;
node10.right = NULL;
node11.left = NULL;
node11.right = NULL;
node12.left = NULL;
node12.right = NULL;
node13.left = NULL;
node13.right = NULL;
node14.left = NULL;
node14.right = NULL;
start_print(&head1);
return 0;
}
4 運(yùn)行結(jié)果
2
3
1
3
2
4
1
5
5
2
1
4
3
2
3
5 總結(jié)
void start_print(Node *head)
{
if (head == NULL)
{
std::cout << "head is NULL" << std::endl;
return;
}
std::stack<Node *> stack;
stack.push(head);
while (stack.size())
{
Node *node = stack.top();
std::cout << node->value << std::endl;
if (node->right)
{
stack.push(node->right);
}
if (node->left)
{
stack.push(node->left);
}
//do not remember pop node
stack.pop();
}
}
一開(kāi)始我出現(xiàn)了2個(gè)問(wèn)題
問(wèn)題1:沒(méi)有調(diào)用stack.pop()函數(shù),導(dǎo)致死循環(huán)。
問(wèn)題2:我把那個(gè)stack.pop()寫(xiě)出上面的那個(gè)位置,很明顯這里是棧,如果node->right或者node->left加到棧里面去了,這個(gè)時(shí)候再?gòu)棾鰜?lái)肯定不是我想要的效果,受之前使用queue的影響,因?yàn)閜op()函數(shù)放哪里都行,想下如果是queue的話,因?yàn)槭窍冗M(jìn)先出,所以如果node->right或者node->left加到隊(duì)列里面去了,再pop()依然是彈出的最頂上的位置,所以不受位置限制。
小結(jié):要記得使用pop()函數(shù)彈出來(lái),然后stack調(diào)用pop()函數(shù)有位置限制,但是queue沒(méi)有限制。
作者:chen.yu
深信服三年半工作經(jīng)驗(yàn),目前就職游戲廠商,希望能和大家交流和學(xué)習(xí),
微信公眾號(hào):編程入門(mén)到禿頭 或掃描下面二維碼
零基礎(chǔ)入門(mén)進(jìn)階人工智能(鏈接)