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

糖逗

题目描述：

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. [
    
16.   [3],
    
17.   [9,20],
    
18.   [15,7]
    
19. ]
    
20.  
    
21. 
    
22. 提示：
    
23. 
    
24. 节点总数 <= 1000
    
25. 
    
26. 来源：力扣（LeetCode）
    
27. 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
    
28. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. #include <malloc.h>
   
5. 
   
6. using namespace std;
   
7. 
   
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. 
    
18. TreeNode* CreateTree(vector<int>& input){
    
19.         TreeNode* tree = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    
20.         for(int i = 0; i < input.size() ;i++){
    
21.                 tree[i].val = input[i];
    
22.                 tree[i].left = NULL;
    
23.                 tree[i].right = NULL;
    
24.                
    
25.         }
    
26.         for(int i = 0; i <= input.size()/2-1; i++){
    
27.                 if(2*i+1 <= input.size()){
    
28.                         tree[i].left = &tree[2*i+1];
    
29.                 }
    
30.                 if(2*i+2<=input.size()){
    
31.                         tree[i].right = &tree[2*i+2];
    
32.                 }
    
33.         }
    
34.         return tree;
    
35. }
    
36. 
    
37. vector<vector<int> > solution(TreeNode* root){
    
38.         vector<vector<int> > res;
    
39.         if(root == NULL) return res;
    
40.         queue<TreeNode*> temp;
    
41.         temp.push(root);
    
42.         while(!temp.empty()){
    
43.                 vector<int> temp1;
    
44.                 int length = temp.size();
    
45.                 for(int i = 0; i < length; i++){
    
46.                         TreeNode* node = temp.front();
    
47.                         temp1.push_back(node -> val);
    
48.                         temp.pop();
    
49.                         if(node -> left) temp.push(node -> left);
    
50.                         if(node -> right) temp.push(node -> right);
    
51.                        
    
52.                 }
    
53.                 res.push_back(temp1);
    
54.         }
    
55.        
    
56.         return res;
    
57. }
    
58. 
    
59. 
    
60. 
    
61. int main(void){
    
62.         vector<int>input;
    
63.         int number;
    
64.         cout << "please send numbers for this tree:" << endl;
    
65.         while(cin >> number){
    
66.                 input.push_back(number);
    
67.         }
    
68.         TreeNode* root = CreateTree(input);
    
69.         vector<vector<int> > res = solution(root);
    
70.         for(int i = 0; i < res.size(); i++){
    
71.                 for(int j = 0; j < res[i].size();j++){
    
72.                         if(res[i][j] == 0){
    
73.                                 cout  << " ";
    
74.                         }
    
75.                         else{
    
76.                                 cout << res[i][j];
    
77.                         }
    
78.                        
    
79.                 }
    
80.                 cout << endl;
    
81.         }
    
82. 
    
83.         return 0;
    
84. }
    
85. 
    
86. 
    

复制代码

注意事项：
1.一层层打印。
2.细节有很多坑。

糖逗

新增代码

1. vector<vector<int> > solution(TreeNode* root){
   
2.         vector<vector<int> > res;
   
3.         if(root == NULL) return res;
   
4.         queue<TreeNode*> temp;
   
5.         temp.push(root);
   
6.         while(!temp.empty()){
   
7.                 vector<int> temp1;
   
8.                 int length = temp.size();
   
9.                 for(int i = 0; i < length; i++){
   
10.                         TreeNode* node = temp.front();
    
11.                         temp1.push_back(node -> val);
    
12.                         temp.pop();
    
13.                         if(node -> left) temp.push(node -> left);
    
14.                         if(node -> right) temp.push(node -> right);
    
15.                        
    
16.                 }
    
17.                 res.push_back(temp1);
    
18.         }
    
19.       
    
20.         return res;
    
21. }

复制代码

糖逗

同类型题：513. 找树左下角的值
题目描述：

1. 
   
2. 给定一个二叉树，在树的最后一行找到最左边的值。
   
3. 
   
4. 示例 1:
   
5. 
   
6. 输入:
   
7. 
   
8.     2
   
9.    / \
   
10.   1   3
    
11. 
    
12. 输出:
    
13. 1
    
14. 
    
15. 
    
16. 示例 2:
    
17. 
    
18. 输入:
    
19. 
    
20.         1
    
21.        / \
    
22.       2   3
    
23.      /   / \
    
24.     4   5   6
    
25.        /
    
26.       7
    
27. 
    
28. 输出:
    
29. 7
    
30. 
    
31. 
    
32. 注意: 您可以假设树（即给定的根节点）不为 NULL。

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     int findBottomLeftValue(TreeNode* root) {
    
13.         //广度优先搜索
    
14.         if(root == NULL) return 0;
    
15.         queue<TreeNode*> store;
    
16.         store.push(root);
    
17.         vector<int> res;
    
18.         vector<int> res1;
    
19.         while(!store.empty()){
    
20.             vector<int> res;
    
21.             int len = store.size();
    
22.             for(int i = 0; i < len; i++){
    
23.                 TreeNode* temp = store.front();
    
24.                 res.push_back(temp -> val);
    
25.                 store.pop();
    
26.                 if(temp -> left) store.push(temp -> left);
    
27.                 if(temp -> right) store.push(temp -> right);
    
28.             }
    
29.             res1 = res;
    
30.         }
    
31.         return res1[0];
    
32.     }
    
33. };

复制代码