-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathoffer_32
82 lines (73 loc) · 1.82 KB
/
offer_32
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//面试题32：从上到下打印二叉树（层序遍历）
//题目1：不分行从上到下打印二叉树
void PrintFromTopToBottom(BinaryTreeNode* pTreeRoot)
{
if(pTreeRoot==nullptr)
return;
std::deque<BinaryTreeNode*> dequeTreeNode;
dequeTreeNode.push_back(pTreeRoot);
while(dequeTreeNode.size()){
BinaryTreeNode* pNode=dequeTreeNode.front();
dequeTreeNode.pop_front();
printf("%d",pNode->m_nValue);
if(pNode->m_pLeft)
dequeTreeNode.push_back(pNode->m_pLeft);
if(pNode->m_pRight)
dequeTreeNode.push_back(pNode->m_pRight);
}
}
//题目2：分行从上到下打印二叉树
void Print(BinaryTreeNode* pRoot)
{
if(pRoot==nullptr)
return;
std::queue<BinaryTreeNode*> nodes;
nodes.push(pRoot);
int nextLevel=0;
int toBePrinted=1;
while(!nodes.empty()){
BinaryTreeNodes* pNode=nodes.front();
printf("%d",pNodes->m_nValue);
if(pNodes->m_pLeft!=nullptr){
nodes.push(pNode->m_pLeft);
++nextLevel;
}
if(pNodes->m_pRight!=nullptr){
nodes.push(pNode->m_nRight);
++nextLevel;
}
nodes.pop();
--toBePrinted;
if(toBePrinted==0){
printf("\n");
toBePrinted=nextLevel;
nextLevel=0;
}
}
}
//题目3：之字形打印二叉树
void Print(BinaryTreeNode* pRoot)
{
if(pRoot==nullptr)
return;
std::stack<BinaryTreeNode*> level[2];
int current=0;
int next=1;
level[current].push(pRoot);
if(current==0){
if(pNode->m_pLeft!=nullptr)
level[next].push(pNode->m_pLeft);
if(pNode->m_pRight!=nullptr)
level[next].push(pNode->m_pRight);
}else{
if(pNode->m_pRight!=nullptr)
level[next].push(pNode->m_pRight);
if(pNode->m_pLeft!=nullptr)
level[next].push(pNode->m_pLeft);
}
if(levels[current].empty()){
printf("\n");
current=1-current;
next=1-next;
}
}