【题目】
Given a binary tree, return thezigzag level ordertraversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree{3,9,20,#,#,15,7}
,
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
confused what"{1,#,2,3}"
means?>
read more on how binary tree is serialized on OJ.
【代码一】
/*********************************
* 日期:2014-12-09
* 作者:SJF0115
* 题号: 103.Binary Tree Zigzag Level Order Traversal
* 来源:https://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <malloc.h>
#include <stack>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<int> level;
vector<vector<int> > levels;
if(root == NULL){
return levels;
}
queue<TreeNode*> curq,nextq;
stack<TreeNode*> curs,nexts;
// 第index层
int index = 1;
//入队列
curq.push(root);
// 层次遍历
while(!curq.empty() || !curs.empty()){
//当前层遍历
while(!curq.empty() || !curs.empty()){
TreeNode *p,*q;
// 第奇数层用队列存储
if(index & 1){
p = curq.front();
curq.pop();
// 第偶数层用栈存储下一层节点
//左子树
if(p->left){
nexts.push(p->left);
// 用于从左到右遍历节点
nextq.push(p->left);
}
//右子树
if(p->right){
nexts.push(p->right);
//用于从左到右遍历
nextq.push(p->right);
}
}
// 第偶数层用栈存储
else{
p = curs.top();
curs.pop();
// 存储节点时都是从左到右遍历
q = curq.front();
curq.pop();
// 第奇数层用队列存储下一层节点
//左子树
if(q->left){
nextq.push(q->left);
}
//右子树
if(q->right){
nextq.push(q->right);
}
}
level.push_back(p->val);
}
index++;
levels.push_back(level);
level.clear();
swap(nextq,curq);
swap(nexts,curs);
}//while
return levels;
}
};
//按先序序列创建二叉树
int CreateBTree(TreeNode* &T){
char data;
//按先序次序输入二叉树中结点的值(一个字符),‘#’表示空树
cin>>data;
if(data == '#'){
T = NULL;
}
else{
T = (TreeNode*)malloc(sizeof(TreeNode));
//生成根结点
T->val = data-'0';
//构造左子树
CreateBTree(T->left);
//构造右子树
CreateBTree(T->right);
}
return 0;
}
int main() {
Solution solution;
TreeNode* root(0);
CreateBTree(root);
vector<vector<int> > vecs = solution.zigzagLevelOrder(root);
for(int i = 0;i < vecs.size();i++){
for(int j = 0;j < vecs[i].size();j++){
cout<<vecs[i][j];
}
cout<<endl;
}
}
【代码二】
//广度优先遍历,用一个 bool 记录是从左到右还是从右到左,每一层结束就翻转一下。
// 迭代版,时间复杂度 O(n),空间复杂度 O(n)
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<int> level;
vector<vector<int> > levels;
if(root == NULL){
return levels;
}
queue<TreeNode*> queue;
// 从左到右
bool isLR = true;
//入队列
queue.push(root);
// 层次分割标志
queue.push(NULL);
// 层次遍历
while(!queue.empty()){
TreeNode* p = queue.front();
queue.pop();
// 访问当前层
if(p){
level.push_back(p->val);
// 左子节点
if(p->left){
queue.push(p->left);
}
// 右子节点
if(p->right){
queue.push(p->right);
}
}
// 当前层访问完毕
else{
// 从左到右
if(isLR){
levels.push_back(level);
}
else{
// 反转
reverse(level.begin(), level.end());
levels.push_back(level);
}
level.clear();
isLR = !isLR;
// 判断是当前层访问完毕还是全部访问完毕
if(queue.size() > 0){
queue.push(NULL);
}
}
}//while
return levels;
}
};
分享到:
相关推荐
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
103 Binary Tree Zigzag Level Order Traversal.js(二叉树之字形级别顺序Traversal.js) 104 Binary Tree.js的最大深度 105从Preorder和Inorder Traversal.js构造二叉树 106从有序和后置Traversal.js构造二叉树 ...
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
lru缓存leetcode 1 https://leetcode.com/problems/two-sum/ Two ...https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ Binary Tree Zigzag Level Order Traversal 104 htt
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
原创:leetcode 111. 二叉树的最小深度记住:最小深度和最大深度方法不同。* Definition for a binary tree node.in
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
Leetcode 题解.pdf
LeetCode 后端.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
Leetcode101.zip
Recording personal Java, Python, JavaScript solutions for Leetcode problems. 记录个人 Java, Python, JavaScript 的Leetcode题解.zip
刷leetcode总结.md
原创:leetcode 5. 最长回文子串//寻找以i-1,i为中点偶数长度的回文//寻找以i为中心的奇数长度的回文。
My Solutions to Leetcode problems. All solutions support C