103. Binary Tree Zigzag Level Order Traversal

题目链接

题目大意

就是给定一个二叉树,返回这个二叉树按照“之”字形层序遍历的结果。

比如,第一层从左向右,第二层从右向左,第三层从左向右。。。以此类推。

解题思路

这道题是刷牛客网上《剑指offer》题目看到的,最简单的方法肯定是按照常规层序遍历,这是每次加个判断来决定是否反转当前层。

但是反转肯定也是需要花费时间的,我于是找到了leetcode上的一篇最优解,发现思路还是很简单、巧妙的。

首先在我们知道当前进入循环前当前队列中元素的个数,就是这一层元素的个数。那么,我们就可以建立一个以这个个数 sizevector ,遍历存储的时候,位置由 leftToRight 这个标志决定,从左向右,那么就是当前下标,反之,就是 size - 1 - i ,应该很好理解。

比如,当前队列元素为[9, 20, 8],如果是从右向左,那么9这个数字应该存放在 vector 中的第 3 - 1 - 0 ,也就是下标为2的位置。

这样,就省去了反转的过程,最终,leetcode提交的速度也是平均击败了95%以上的提交。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector <vector <int>> res;
if (nullptr == root) return res;
queue <TreeNode *> q;
q.push(root);
bool leftToRight = true;
while (!q.empty())
{
int thisSize = q.size();
vector <int> level(thisSize);
for (int i = 0; i < thisSize; ++i) {
TreeNode * node = q.front();
int index = leftToRight ? i : thisSize - 1 - i;
level[index] = node -> val;
if (nullptr != node -> left) q.push(node -> left);
if (nullptr != node -> right) q.push(node -> right);
q.pop();
}
leftToRight = !leftToRight;
res.push_back(level);
}
return res;
}
};
文章作者: Yeoman Li
文章链接: https://yeomanli.github.io/2019/05/24/103.-Binary-Tree-Zigzag-Level-Order-Traversal/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yeoman's Blog