首页 > > 程序设计 > C/C++ >

剑指offer22：从上往下打印出二叉树的每个节点，…

2019-08-26 05:40:17来源：博客园阅读 ()

剑指offer22：从上往下打印出二叉树的每个节点，同层节点从左至右打印。

1 题目描述

　　从上往下打印出二叉树的每个节点，同层节点从左至右打印。

2 思路和方法

　　使用一个队列存放节点。先将根节点加入到队列中，然后循环遍历队列中的元素，遍历过程中，访问该节点的左右子节点，再将左右子节点加入到队列中。

　　例子：1 2 3 4 5 6 7 8

　　对于第一层，只有根节点 1,第二层有节点2和3。先将根节点1加入到队列中，接下来要打印节点为1的两个子节点，应该在遍历到该根节点时把值为2和3的两个子节点保存到队列。按照从左向右打印的要求，取出2，保存其子节点4；随后取出3，保存其子节点“5”和“6”；随后取出4，保存子节点“7”；随后取出5，子节点NULL，不保存；返回上一层6，取出6，保存子节点8；取出7，取出8。

3 C++核心代码

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     vector<int> PrintFromTopToBottom(TreeNode* root) {
13         vector<int> res;
14         if (root == nullptr) return res;
15         queue<TreeNode*> que;
16         que.push(root);
17         while (!que.empty())
18         {
19             TreeNode* node = que.front();
20             if (node->left){
21                 que.push(node->left);
22             }
23             if (node->right){
24                 que.push(node->right);
25             }
26             res.push_back(node->val);
27             que.pop();
28         }
29         return res;
30     }
31 };

View Code

4 C++完整代码

 1 #include<iostream>
 2 #include <vector>
 3 #include <queue>
 4 
 5 using namespace std;
 6 
 7 struct TreeNode {
 8     int val;
 9     struct TreeNode *left;
10     struct TreeNode *right;
11     TreeNode(int x) :
12         val(x), left(NULL), right(NULL) {
13     }
14 };
15 
16 class Solution {
17 public:
18     vector<int> PrintFromTopToBottom(TreeNode* root) {
19         vector<int> res;
20         if (root == nullptr) return res;
21         queue<TreeNode*> que;
22         que.push(root);
23         while (!que.empty())
24         {
25             TreeNode* node = que.front();
26             if (node->left){
27                 que.push(node->left);
28             }
29             if (node->right){
30                 que.push(node->right);
31             }
32             res.push_back(node->val);
33             que.pop();
34         }
35         return res;
36     }
37 };
38 
39 int main()
40 {
41     Solution* s = new Solution();
42     TreeNode* t1 = new TreeNode(1);
43     TreeNode* t2 = new TreeNode(2);
44     TreeNode* t3 = new TreeNode(3);
45     TreeNode* t4 = new TreeNode(4);
46     TreeNode* t5 = new TreeNode(5);
47     t1->left = t2;
48     t1->right = t3;
49     t2->left = t4;
50     t2->right = t5;
51     s->PrintFromTopToBottom(t1);
52     //cout <<  << endl;
53 
54     system("pause");
55     return 0;
56 }