LeetCode: 103_Binary Tree Zigzag Level Order Traversal | 二叉树Zigzag层次遍历 | Medium

本题也属于层次遍历的变形,不同之处在于其遍历的方法是交替进行的,形成一个ZigZag的曲线形式,如下:

代码如下:

 1 struct TreeNode {
 2     int            val;
 3     TreeNode*    left;
 4     TreeNode*    right;
 5     TreeNode(int x): val(x), left(NULL),right(NULL) {}
 6 };
 7 
 8 void Swap(vector<int> &ivec)
 9 {
10     int temp = 0;
11     int len = ivec.size();
12     for (int i = 0; i < len/2; i ++) {
13         temp = ivec.at(i);
14         ivec.at(i) = ivec.at(len-1-i);
15         ivec.at(len-1-i) = temp;
16     }
17 }
18 
19 vector<vector <int> > zigzagLevelOrder(TreeNode *root)
20 {
21     vector<vector<int> > tree_vector;
22     vector<int> ivec;
23     queue<TreeNode *> tree_queue;
24     if (NULL == root)
25         return tree_vector;
26 
27     tree_queue.push(root);
28     tree_queue.push(NULL);
29     int nLevelCount = 1;
30     while (true) {
31         TreeNode *pTemp = tree_queue.front();
32         tree_queue.pop();
33         if (pTemp == NULL) {
34             if (nLevelCount%2 == 0) { //if the num of level is odd, swap the ivec;
35                 Swap(ivec);
36             }
37             tree_vector.push_back(ivec);
38             ivec.clear();
39             if (tree_queue.empty())
40                 break;
41             tree_queue.push(NULL);
42             nLevelCount ++;
43         }
44         else {
45             ivec.push_back(pTemp->val);
46             if (pTemp->left)
47                 tree_queue.push(pTemp->left);
48             if (pTemp->right)
49                 tree_queue.push(pTemp->right);
50         }
51     }
52     return tree_vector;
53 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

codeforces736D. Permutations(线性代数)

752
来自专栏数据结构与算法

BZOJ2118: 墨墨的等式(最短路 数论)

这里有一篇讲的非常好的博客https://blog.csdn.net/w4149/article/details/66476606?locationNum=3&...

661
来自专栏linux、Python学习

必备神技能 | MySQL 查找删除重复行

本文讲述如何查找数据库里重复的行。这是初学者十分普遍遇到的问题。方法也很简单。这个问题还可以有其他演变,例如,如何查找“两字段重复的行”(#mysql IRC ...

710
来自专栏GreenLeaves

SQL学习之汇总数据之聚集函数

一、 1、我们经常需要汇总数据而不用把他们实际检索出来,为此SQL提供了专门的函数,以便于分析数据和报表生成,这些函数的功能有: (1)确定表中行数(或者满足单...

1995
来自专栏行者常至

006.python科学计算库matplotlib(上)

版权声明:本文为博主原创文章,允许转载,请标明出处。 https://blog.csdn.net/qwdafedv/article/deta...

681
来自专栏hadoop学习笔记

hanlp源码解析之中文分词算法详解

词图指的是句子中所有词可能构成的图。如果一个词A的下一个词可能是B的话,那么A和B之间具有一条路径E(A,B)。一个词可能有多个后续,同时也可能有多个前驱,它们...

1033
来自专栏数据结构与算法

BZOJ 4520: [Cqoi2016]K远点对(k-d tree)

1210
来自专栏hbbliyong

使用WPF教你一步一步实现连连看(三)

这次首先对以前的结构进行了调整: 第一步:把MyButton按钮的属性独立成一个类,放在一个单独的MyButton.cs中,把图片的初始化也放到里面。 调整代...

3487
来自专栏hanlp学习笔记

hanlp源码解析之中文分词算法

词图指的是句子中所有词可能构成的图。如果一个词A的下一个词可能是B的话,那么A和B之间具有一条路径E(A,B)。一个词可能有多个后续,同时也可能有多个前驱,它们...

1572
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[03]:熟练图元绘制,玩转二维图形

文章的大前提是,你得有《OpenGL ES 2.0 (iOS): 一步从一个小三角开始》的基础知识。

1911

扫码关注云+社区