# 【leetcode刷题】T116-二叉树的锯齿形层次遍历

`二叉树`类型第6篇解题报告

leetcode第103题：二叉树的锯齿形层次遍历

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

【题目】

```例如：

3
/ \
9  20
/  \
15   7

[
[3],
[20,9],
[15,7]
]```

【思路】

【代码】

python版本

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
res = []
num = []
tmp1 = [root]
tmp2 = []
reverse = False
while len(tmp1) != 0 or len(tmp2) != 0:
if len(tmp1) == 0:
tmp1 = copy.copy(tmp2)
tmp2 = []
if reverse:
reverse = False
num = num[::-1]
else:
reverse = True
res.append(num)
num = []
p = tmp1.pop(0)
num.append(p.val)
if p.left:
tmp2.append(p.left)
if p.right:
tmp2.append(p.right)
if reverse:
num = num[::-1]
res.append(num)
return res```

C++版本

```/**
* Definition for a binary tree node.
* 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<vector<int>> res;
if(!root)
return res;
vector<int> num;
vector<TreeNode*> tmp1;
vector<TreeNode*> tmp2;
tmp1.push_back(root);
TreeNode* p = NULL;
bool should_reverse = false;
while(tmp1.size() != 0 || tmp2.size() != 0){
// tmp1为空，tmp2非空
if(tmp1.size() == 0){
for(int i=0; i<tmp2.size(); i++){
tmp1.push_back(tmp2[i]);
}
tmp2.erase(tmp2.begin(), tmp2.end());
if(should_reverse){
reverse(num.begin(), num.end());
should_reverse = false;
}else{
should_reverse = true;
}
res.push_back(num);
num.erase(num.begin(), num.end());
}
p = tmp1[0];
num.push_back(p->val);
tmp1.erase(tmp1.begin());
if(p->left)
tmp2.push_back(p->left);
if(p->right)
tmp2.push_back(p->right);
}
if(should_reverse){
reverse(num.begin(), num.end());
}
res.push_back(num);
return res;
}
};```

0 条评论

• ### 【leetcode刷题】20T14-有效的括号

https://leetcode-cn.com/problems/valid-parentheses/

• ### 【leetcode刷题】T61-整数转罗马数字

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II ...

• ### 面向方面编程的介绍----基本概念（1）

<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

• ### 动手学深度学习(十一) NLP循环神经网络

本节介绍循环神经网络，下图展示了如何基于循环神经网络实现语言模型。我们的目的是基于当前的输入与过去的输入序列，预测序列的下一个字符。循环神经网络引入一个隐藏变量

• ### 使用HanLP增强Elasticsearch分词功能

hanlp-ext 插件源码地址：http://git.oschina.net/hualongdata/hanlp-ext 或 https://github.c...

• ### ElasticSearch实战系列02：中文+拼音混合检索，并高亮显示

本文仿照QQ的用户搜索，搭建一个中文+拼音的混合检索系统，并高亮显示检索字段。全文共分为以下几部分：

• ### 一湖数据，几度春秋

2017年底的一场reorg，让微软的Azure Data Lake（数据湖）队伍拆的七零八落，Raghu Ramakrishnan也黯然神伤，被reorg成了...

• ### ElasticSearch中文分词器-IK分词器的使用

得到如下结果，可以发现es的默认分词器无法识别中文中农业、银行这样的词汇，而是简单的将每个字拆完分为一个词，这显然不符合我们的使用要求。