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

糖逗

题目描述：

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

 

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]
 

提示：

节点总数 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <iostream>
#include <vector>
#include <queue>
#include <malloc.h>

using namespace std;


struct TreeNode{
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x): val(x), left(NULL), right(NULL){
        }
};


TreeNode* CreateTree(vector<int>& input){
        TreeNode* tree = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
        for(int i = 0; i < input.size() ;i++){
                tree[i].val = input[i];
                tree[i].left = NULL;
                tree[i].right = NULL;
                
        }
        for(int i = 0; i <= input.size()/2-1; i++){
                if(2*i+1 <= input.size()){
                        tree[i].left = &tree[2*i+1]; 
                }
                if(2*i+2<=input.size()){
                        tree[i].right = &tree[2*i+2];
                }
        }
        return tree;
}

vector<vector<int> > solution(TreeNode* root){
        vector<vector<int> > res;
        if(root == NULL) return res;
        queue<TreeNode*> temp;
        temp.push(root);
        while(!temp.empty()){
                vector<int> temp1;
                int length = temp.size();
                for(int i = 0; i < length; i++){
                        TreeNode* node = temp.front();
                        temp1.push_back(node -> val);
                        temp.pop();
                        if(node -> left) temp.push(node -> left);
                        if(node -> right) temp.push(node -> right);
                        
                }
                res.push_back(temp1);
        }
        
        return res;
}



int main(void){
        vector<int>input;
        int number;
        cout << "please send numbers for this tree:" << endl;
        while(cin >> number){
                input.push_back(number);
        }
        TreeNode* root = CreateTree(input);
        vector<vector<int> > res = solution(root);
        for(int i = 0; i < res.size(); i++){
                for(int j = 0; j < res[i].size();j++){
                        if(res[i][j] == 0){
                                cout  << " ";
                        }
                        else{
                                cout << res[i][j];
                        }
                        
                }
                cout << endl;
        }

        return 0;
}

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

糖逗

新增代码

vector<vector<int> > solution(TreeNode* root){
        vector<vector<int> > res;
        if(root == NULL) return res;
        queue<TreeNode*> temp;
        temp.push(root);
        while(!temp.empty()){
                vector<int> temp1;
                int length = temp.size();
                for(int i = 0; i < length; i++){
                        TreeNode* node = temp.front();
                        temp1.push_back(node -> val);
                        temp.pop();
                        if(node -> left) temp.push(node -> left);
                        if(node -> right) temp.push(node -> right);
                       
                }
                res.push_back(temp1);
        }
       
        return res;
}

糖逗

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

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:
1
 

示例 2:

输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:
7
 

注意: 您可以假设树（即给定的根节点）不为 NULL。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        //广度优先搜索
        if(root == NULL) return 0;
        queue<TreeNode*> store;
        store.push(root);
        vector<int> res;
        vector<int> res1;
        while(!store.empty()){
            vector<int> res;
            int len = store.size();
            for(int i = 0; i < len; i++){
                TreeNode* temp = store.front();
                res.push_back(temp -> val);
                store.pop();
                if(temp -> left) store.push(temp -> left);
                if(temp -> right) store.push(temp -> right);
            }
            res1 = res;
        }
        return res1[0];
    }
};