中国信用网企业查询系统,网站优化工作室,网站建设的步骤有哪些,网站开发的软件介绍题目链接#xff1a; http://www.lintcode.com/zh-cn/problem/binary-tree-zigzag-level-order-traversal/ 二叉树的锯齿形层次遍历 给出一棵二叉树#xff0c;返回其节点值的锯齿形层次遍历#xff08;先从左往右#xff0c;下一层再从右往左#xff0c;层与层之间交替进… 题目链接 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:vectorvectorint zigzagLevelOrder(TreeNode *root) {// write your code herevectorvectorint vv;if(root NULL) return vv;dequeTreeNode * q;q.push_back(root);bool dir true;//true表示从左向右存储层次遍历否则是从右向左int levelCnt 1;//上一层的节点数目int curLevelCnt 0;//下一层节点数目vectorint 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;}
};
