lintcode二叉树的锯齿形层次遍历 (双端队列)
2023-09-27 14:20:24 时间
题目链接:
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 = 1;//上一层的节点数目 int curLevelCnt = 0;//下一层节点数目 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 == 0){//这一层完毕 vv.push_back(v); v.clear(); levelCnt = curLevelCnt; curLevelCnt = 0; dir = !dir; } } return vv; } };
相关文章
- [LintCode] Binary Tree Level Order Traversal(二叉树的层次遍历)
- C#实现二叉树非递归中序遍历程序
- C语言:求平衡二叉树的高度算法
- LeetCode 107 Binary Tree Level Order Traversal II(二叉树的层级顺序遍历2)(*)
- 二叉树的遍历
- LeetCode_二叉树_中等_114.二叉树展开为链表
- 1366:二叉树输出(btout)
- leetcode 104.二叉树的最大深度
- LeetCode·二叉树前序、中序、后序遍历·递归
- Java二叉树递推遍历
- 二叉树的递归遍历——天平(递归输入)
- 先序遍历-二叉树
- 关于二叉树的几种遍历方法
- 二叉树——LCA问题
- 高级数据结构 | 二叉树遍历 —递归与非递归实现:先序、中序、后序遍历二叉树 ...
- [LeetCode] 545. Boundary of Binary Tree 二叉树的边界
- 李洪强iOS经典面试题35-按层遍历二叉树的节点
- 给出二叉树的先序和中序遍历,给出后序遍历
- 数据结构:二叉树的遍历——层序遍历、锯齿形遍历
- 数据结构:树的概念 | 二叉树的概念 | 根据前序和中序遍历构建二叉树 | 根据中序和后序遍历构建二叉树
- 【二叉树的后序遍历(145-java)】