lintcode二叉树的锯齿形层次遍历 （双端队列）
2024-10-19 03:24:47
题目链接：
http://www.lintcode.com/zh-cn/problem/binary-tree-zigzag-level-order-traversal/
二叉树的锯齿形层次遍历
给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）
样例
给出一棵二叉树 {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
返回其锯齿形的层次遍历为：
[
[3],
[20,9],
[15,7]
]
思路：
我们用双端队列模拟一下这个过程：开始的时候是正向遍历，3通过push_front()放入队列Q， 形成Q[3]。接着我们规定正向遍历的时候从队列前端去元素，下一层元素放入队列的时候是放入队列的后端；而反向遍历的时候正好相反，唯一不同的就是反向遍历时，下一层的右孩子结点（如果有）先放入队列的前端。
开始Q[3](从前端取数字), 然后下一层放入后是Q[9,20](从后端去数字)，20的下一层放入后是Q[15,7,9], 然后变成Q[15,7](从前端去数字)，最后得到遍历的结果。
代码实现：
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/ class Solution {
/**
* @param root: The root of binary tree.
* @return: A list of lists of integer include
* the zigzag level order traversal of its nodes' values
*/
public:
vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
// write your code here
vector<vector<int>> vv;
if(root == NULL) return vv;
deque<TreeNode *> q;
q.push_back(root);
bool dir = true;//true表示从左向右存储层次遍历，否则是从右向左
int levelCnt = ;//上一层的节点数目
int curLevelCnt = ;//下一层节点数目
vector<int> v;
while(!q.empty()){
TreeNode *cur;
if(dir){
cur = q.front();
q.pop_front();
} else {
cur = q.back();
q.pop_back();
}
if(dir){
if(cur->left){
q.push_back(cur->left);
++curLevelCnt;
}
if(cur->right){
q.push_back(cur->right);
++curLevelCnt;
}
} else {
if(cur->right){
q.push_front(cur->right);
++curLevelCnt;
}
if(cur->left){
q.push_front(cur->left);
++curLevelCnt;
}
}
v.push_back(cur->val);
--levelCnt;
if(levelCnt == ){//这一层完毕
vv.push_back(v);
v.clear();
levelCnt = curLevelCnt;
curLevelCnt = ;
dir = !dir;
}
}
return vv;
}
};
最新文章
- iOS中assign、copy 、retain等关键字的含义
- 管理系统-------------SSH框架书写登录和显示用户
- GDI+系列
- C# 常用加密处理
- 高可用工具keepalived学习笔记
- python & pandas链接mysql数据库
- REST API 基于ACCESS TOKEN 的权限解决方案
- VB.NET版机房收费系统---七仙女之系统登录
- 努比亚 Z5 mini刷机包 omni4.4.2改动V4.0 自用版 精简 MIUI特效
- QQ登录界面
- swift学习 - tableView自适应高度2（SnapKit Layout）
- 直接调用VS.net2005中的配置界面
- mybatis常用配置
- 99%的Linux运维工程师必须要掌握的命令及运用
- struts建立工程helloworld
- 基于vue.js实现远程请求json的select控件
- 《Linux内核设计与实现》Chapter 1 读书笔记
- keepAlive参数详解
- p2 休眠模式
- jqgrid动态填充select