题目描述
题目链接:103. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
例子
Input:
[3,9,20,null,null,15,7]
Output:
[
[3],
[20,9],
[15,7]
]
解题思路
这道题本质上是要求我们按当前层的奇偶性选择从左或者右输出节点值,具体来说:
- 从 0 层开始,当前层为偶数时,从左往右输出
- 奇数时从右往左输出
了解了这一点,可以想到在 bfs 的基础上利用栈的先进后出性质可以很方便的话改变每一层的输出方向。这里注意当我们将子节点压入栈中时也要注意压入的顺序:
- 当前在偶数层时,节点从左往右输出,此时对每一个节点,先压左节点再压右节点,保持相对顺序
- 在奇数层时则相反
代码如下:
#include <vector>
#include <stack>
class Solution {
public:
std::vector<std::vector<int>> zigzagLevelOrder(TreeNode* root) {
std::vector<std::vector<int>> result;
if (root == nullptr) return result;
std::stack<TreeNode*> curr_level_nodes;
curr_level_nodes.push(root);
int curr_level = 0;
while (!curr_level_nodes.empty()) {
std::vector<int> curr_level_vals;
std::stack<TreeNode*> next_level_nodes;
while (!curr_level_nodes.empty()) {
TreeNode* node = curr_level_nodes.top();
curr_level_nodes.pop();
if (curr_level % 2 == 0) {
// if even level, push children from left to right
if (node->left) next_level_nodes.push(node->left);
if (node->right) next_level_nodes.push(node->right);
}
else {
// if odd level, push children from right to left
if (node->right) next_level_nodes.push(node->right);
if (node->left) next_level_nodes.push(node->left);
}
curr_level_vals.push_back(node->val);
}
result.push_back(curr_level_vals);
++curr_level;
curr_level_nodes = next_level_nodes;
}
return result;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(w)
GitHub 代码同步地址: 103.BinaryTreeZigzagLevelOrderTraversal.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions