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).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
分析
广度优先遍历，用一个bool记录是从左到右还是从右到左，每一层结束就翻转一下。
递归版
// Binary Tree Zigzag Level Order Traversal
// 递归版，时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
vector > zigzagLevelOrder(TreeNode *root) {
vector> result;
traverse(root, 1, result, true);
return result;
}
void traverse(TreeNode *root, size_t level, vector> &result,
bool left_to_right) {
if (!root) return;
if (level > result.size())
result.push_back(vector());
if (left_to_right)
result[level-1].push_back(root->val);
else
result[level-1].insert(result[level-1].begin(), root->val);
traverse(root->left, level+1, result, !left_to_right);
traverse(root->right, level+1, result, !left_to_right);
}
};迭代版
// Binary Tree Zigzag Level Order Traversal
// 广度优先遍历，用一个bool记录是从左到右还是从右到左，每一层结束就翻转一下。
// 迭代版，时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
vector > zigzagLevelOrder(TreeNode *root) {
vector > result;
queue current, next;
bool left_to_right = true;
if(root == nullptr) {
return result;
} else {
current.push(root);
}
while (!current.empty()) {
vector level; // elments in one level
while (!current.empty()) {
TreeNode* node = current.front();
current.pop();
level.push_back(node->val);
if (node->left != nullptr) next.push(node->left);
if (node->right != nullptr) next.push(node->right);
}
if (!left_to_right) reverse(level.begin(), level.end());
result.push_back(level);
left_to_right = !left_to_right;
swap(next, current);
}
return result;
}
};