C++刷剑指offer（面试题32 - II. 从上到下打印二叉树 II）【广度优先搜索】
本帖最后由 糖逗 于 2020-5-8 18:11 编辑题目描述：
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: ,
3
/ \
920
/\
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.val = input;
tree.left = NULL;
tree.right = NULL;
}
for(int i = 0; i <= input.size()/2-1; i++){
if(2*i+1 <= input.size()){
tree.left = &tree;
}
if(2*i+2<=input.size()){
tree.right = &tree;
}
}
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.size();j++){
if(res == 0){
cout<< " ";
}
else{
cout << res;
}
}
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;
}
};
页:
[1]