C++刷剑指offer(面试题32 - III. 从上到下打印二叉树 III)【广度优先搜索】
本帖最后由 糖逗 于 2020-5-8 17:44 编辑题目描述：
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: ,
3
/ \
920
/\
15 7
返回其层次遍历结果：
[
,
,
]
提示：
节点总数 <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <iostream>
#include <vector>
#include <queue>
#include <malloc.h>
#include <algorithm>
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);
}
if(res.size()%2 == 1) reverse(temp1.begin(), temp1.end());
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.和之前的代码一样:https://fishc.com.cn/thread-163200-1-1.html
知识新增了一行代码
if(res.size()%2 == 1) reverse(temp1.begin(), temp1.end());
相似题型：116. 填充每个节点的下一个右侧节点指针
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：
输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if(root == NULL) return root;
queue<Node*> temp;
temp.push(root);
while(!temp.empty()){
int len = temp.size();
Node* temp1 = NULL;
for(int i = 0; i < len; i++){
Node* node = temp.front();
temp.pop();
if(node == NULL) continue;
node -> next = temp1;
temp1 = node;
temp.push(node -> right);
temp.push(node -> left);
}
}
return root;
}
};
注意事项：1.temp.pop();的书写位置在continue前面。 你下次弄成悬赏贴人会很多(我估计）
页:
[1]