题目描述:
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
实例:
例如:
给定二叉树 [3,9,20,null,null,15,7]
返回锯齿形层次遍历如下:
[
[3],
[20,9],
[15,7]
]
解题思路
本题要求在常规的队列+BFS
基础上进行“之字形”遍历。说明我们要对BFS的过程做出一些调整。
我们观察发现,假设从第0
层开始算起,偶数层输出顺序从左到右,而奇数层输出顺序从右到左。通常来说,我们一般习惯的输出顺序为从左到右,所以只需要一个队列利用其先进先出的特性即可完成需求。现在,我们可能会想念栈,因为栈的特点是先进后出,符合奇数层输出顺序。
这时,我们需要引入c++ STL库中的一个容器——deque,也就是我们熟悉的双端队列。它可以同时实现先进先出和先进后出两个特点。也就是说从左到右,我们可以push_back()
,即常规地从队尾进队;也可以push_front()
,即从队头进队。
代码
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 27 28 29 30 31
| class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> result; if(!root) return result; queue<TreeNode*> queue_Tree; queue_Tree.push(root); int height = 0; while(!queue_Tree.empty()){ int n = queue_Tree.size(); deque<int> deque_Tree; for(int i = 0; i < n; i++){ TreeNode* node = queue_Tree.front(); queue_Tree.pop(); if(height % 2 == 0) deque_Tree.push_back(node->val); else deque_Tree.push_front(node->val); if(node->left) queue_Tree.push(node->left); if(node->right) queue_Tree.push(node->right); } height++; result.push_back( vector<int>( deque_Tree.begin(), deque_Tree.end() ) ); } return result; } };
|
如果有错误或者不严谨的地方,请务必给予指正,十分感谢。