C++刷剑指offer（面试题32 - I. 从上到下打印二叉树）【广度优先搜索】
本帖最后由 糖逗 于 2020-4-6 13:04 编辑题目描述：
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: ,
3
/ \
920
/\
15 7
返回：
提示：
节点总数 <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include<iostream>
#include <malloc.h>
#include <vector>
#include <math.h>
#include <queue>
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* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
for(int i = 0; i < input.size(); i++){
res.val = input;
res.left = NULL;
res.right = NULL;
}
for(int i= 0; i < input.size(); i++){
if(2*i+1 < input.size()){
res.left = &res;
}
if(2*i+2 < input.size()){
res.right = &res;
}
}
return res;
}
void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
if(root == NULL) return;
int insert = left + (right - left) / 2;
res = root->val;
middle(root->left, res, left, insert - 1, depth + 1);
middle(root->right, res, insert + 1, right, depth + 1);
}
int treeDepth(TreeNode* root){
if(root == NULL || root -> val == 0) return 0;
return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
}
void printTree(TreeNode* root) {
int depth = treeDepth(root);
int width = pow(2, depth) - 1;
vector<vector<int> > res(depth, vector<int>(width, 0));
middle(root, res, 0, width - 1, 0);
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;
}
cout << "------------------" << endl;
}
vector<int> solution(TreeNode* root) {
vector<int> res;
if(root == NULL) return res;
queue <TreeNode*> temp;
temp.push(root);
while(!temp.empty()){
auto node = temp.front();
temp.pop();
res.push_back(node -> val);
if(node -> left != NULL) temp.push(node -> left);
if(node -> right != NULL) temp.push(node -> right);
}
return res;
}
int main(void){
vector<int> input;
cout << "send numbers for the tree" << endl;
int number;
while(cin >> number){
input.push_back(number);
}
TreeNode* root = CreateTree(input);
printTree(root);
vector<int> res= solution(root);
for(int i = 0; i < res.size(); i++){
if(res != 0){
cout << res << " ";
}
}
return 0;
}
注意事项：
1.用到广度优先搜索。
2.广度优先搜索一般使用队列辅助求解。
3.参考链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/solution/mian-shi-ti-32-i-cong-shang-dao-xia-da-yin-er-ch-4/ 新增代码
vector<int> solution(TreeNode* root) {
vector<int> res;
if(root == NULL) return res;
queue <TreeNode*> temp;
temp.push(root);
while(!temp.empty()){
auto node = temp.front();
temp.pop();
res.push_back(node -> val);
if(node -> left != NULL) temp.push(node -> left);
if(node -> right != NULL) temp.push(node -> right);
}
return res;
}
页:
[1]