C++刷剑指offer（面试题32 - I. 从上到下打印二叉树）【广度优先搜索】

糖逗

题目描述：

1. 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
   
2. 
   
3.  
   
4. 
   
5. 例如:
   
6. 给定二叉树: [3,9,20,null,null,15,7],
   
7. 
   
8.     3
   
9.    / \
   
10.   9  20
    
11.     /  \
    
12.    15   7
    
13. 返回：
    
14. 
    
15. [3,9,20,15,7]
    
16.  
    
17. 
    
18. 提示：
    
19. 
    
20. 节点总数 <= 1000
    
21. 
    
22. 来源：力扣（LeetCode）
    
23. 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
    
24. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include<iostream>
   
2. #include <malloc.h>
   
3. #include <vector>
   
4. #include <math.h>
   
5. #include <queue>
   
6. 
   
7. using namespace std;
   
8. 
   
9. struct TreeNode{
   
10.         int val;
    
11.         TreeNode* left;
    
12.         TreeNode* right;
    
13.         TreeNode(int x): val(x), left(NULL), right(NULL){
    
14.         }
    
15. };
    
16. 
    
17. TreeNode* CreateTree(vector<int> input){
    
18.         TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    
19.         for(int i = 0; i < input.size(); i++){
    
20.                 res[i].val = input[i];
    
21.                 res[i].left = NULL;
    
22.                 res[i].right = NULL;
    
23.         }
    
24.         for(int i= 0; i < input.size(); i++){
    
25.                 if(2*i+1 < input.size()){
    
26.                         res[i].left = &res[2*i+1];
    
27.                 }
    
28.                 if(2*i+2 < input.size()){
    
29.                         res[i].right = &res[2*i+2];
    
30.                 }
    
31.                
    
32.         }
    
33.         return res;
    
34.        
    
35. }
    
36. 
    
37. void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    
38.     if(root == NULL) return;
    
39.     int insert = left + (right - left) / 2;
    
40.     res[depth][insert] = root->val;
    
41.            
    
42.     middle(root->left, res, left, insert - 1, depth + 1);
    
43.     middle(root->right, res, insert + 1, right, depth + 1);
    
44.     }
    
45. 
    
46. int treeDepth(TreeNode* root){
    
47.     if(root == NULL || root -> val == 0) return 0;
    
48.     return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
    
49. }
    
50.       
    
51. void printTree(TreeNode* root) {
    
52.     int depth = treeDepth(root);
    
53.     int width = pow(2, depth) - 1;
    
54.     vector<vector<int> > res(depth, vector<int>(width, 0));
    
55.     middle(root, res, 0, width - 1, 0);
    
56.     for(int i = 0; i < res.size(); i++){
    
57.                 for(int j = 0; j < res[i].size();j++){
    
58.                         if(res[i][j] == 0){
    
59.                                 cout  << " ";
    
60.                         }
    
61.                         else{
    
62.                                 cout << res[i][j];
    
63.                         }
    
64.                        
    
65.                 }
    
66.                 cout << endl;
    
67.         }
    
68.         cout << "------------------" << endl;
    
69.     }
    
70. 
    
71. 
    
72. vector<int> solution(TreeNode* root) {
    
73.         vector<int> res;
    
74.         if(root == NULL) return res;
    
75.         queue <TreeNode*> temp;
    
76.         temp.push(root);
    
77.         while(!temp.empty()){
    
78.             auto node = temp.front();
    
79.             temp.pop();
    
80.             res.push_back(node -> val);
    
81.             if(node -> left != NULL) temp.push(node -> left);
    
82.             if(node -> right != NULL) temp.push(node -> right);
    
83.         }
    
84.         return res;
    
85. }
    
86. 
    
87. 
    
88. 
    
89. 
    
90. 
    
91. int main(void){
    
92.         vector<int> input;
    
93.         cout << "send numbers for the tree" << endl;
    
94.         int number;
    
95.         while(cin >> number){
    
96.                 input.push_back(number);
    
97.         }
    
98.          
    
99.         TreeNode* root = CreateTree(input);
    
100.         printTree(root);
     
101.         vector<int> res  = solution(root);
     
102.         for(int i = 0; i < res.size(); i++){
     
103.                 if(res[i] != 0){
     
104.                         cout << res[i] << " ";
     
105.                 }
     
106.                
     
107.         }
     
108.        
     
109.         return 0;
     
110. }
     

复制代码

注意事项：
1.用到广度优先搜索。
2.广度优先搜索一般使用队列辅助求解。
3.参考链接：https://leetcode-cn.com/problems ... xia-da-yin-er-ch-4/

糖逗

新增代码

1. vector<int> solution(TreeNode* root) {
   
2.         vector<int> res;
   
3.         if(root == NULL) return res;
   
4.         queue <TreeNode*> temp;
   
5.         temp.push(root);
   
6.         while(!temp.empty()){
   
7.             auto node = temp.front();
   
8.             temp.pop();
   
9.             res.push_back(node -> val);
   
10.             if(node -> left != NULL) temp.push(node -> left);
    
11.             if(node -> right != NULL) temp.push(node -> right);
    
12.         }
    
13.         return res;
    
14. }
    

复制代码