103. Binary Tree Zigzag Level Order Traversal
給定一個二元樹的根節點，返回其節點值的之字形層次遍歷。即首先從左到右進行遍歷，然後下一層從右到左進行遍歷，之後層與層之間交替進行。
範例：
輸入：root = [3,9,20,null,null,15,7] 輸出：[[3],[20,9],[15,7]]
這表明首先遍歷根節點 3，接下來第二層從右到左遍歷，結果是 20 和 9，然後第三層從左到右遍歷，結果是 15 和 7。
Python
from collections import deque
from typing import Optional, List
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
results = []
node_queue = deque([root])
left_to_right = True # Flag to indicate the direction of traversal
while node_queue:
level_size = len(node_queue)
level = deque() # Use deque to facilitate the zigzag order
for _ in range(level_size):
node = node_queue.popleft()
# Append node value in the appropriate direction
if left_to_right:
level.append(node.val)
else:
level.appendleft(node.val)
# Add child nodes in the queue for the next level
if node.left:
node_queue.append(node.left)
if node.right:
node_queue.append(node.right)
results.append(list(level)) # Convert deque to list and add to results
left_to_right = not left_to_right # Toggle the direction for the next level
return results
16.76MB, 32ms
C++
#include <vector>
#include <deque>
#include <queue>
using namespace std;
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> result;
queue<TreeNode*> nodesQueue; // Queue to store the nodes
nodesQueue.push(root);
bool leftToRight = true; // Flag to control the direction of insertion
while (!nodesQueue.empty()) {
int levelSize = nodesQueue.size(); // Number of nodes at the current level
deque<int> levelDeque; // Deque to insert elements in zigzag order
for (int i = 0; i < levelSize; ++i) {
TreeNode* currentNode = nodesQueue.front();
nodesQueue.pop();
// Insert elements in the deque according to the current direction
if (leftToRight) {
levelDeque.push_back(currentNode->val);
} else {
levelDeque.push_front(currentNode->val);
}
// Enqueue left and right children
if (currentNode->left) {
nodesQueue.push(currentNode->left);
}
if (currentNode->right) {
nodesQueue.push(currentNode->right);
}
}
// Convert deque to vector and add to result
result.push_back(vector<int>(levelDeque.begin(), levelDeque.end()));
leftToRight = !leftToRight; // Toggle the direction for the next level
}
return result;
}
};
13.36MB, 0ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var zigzagLevelOrder = function(root) {
if (!root) {
return [];
}
const result = [];
const queue = []; // Using an array to simulate a queue for BFS
queue.push(root);
let leftToRight = true; // Flag to control the direction of insertion
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = []; // Array to hold the current level's values
for (let i = 0; i < levelSize; i++) {
const node = queue.shift(); // Dequeue the front node
// Insert node value in the appropriate direction
if (leftToRight) {
currentLevel.push(node.val);
} else {
currentLevel.unshift(node.val); // Insert at the beginning for reverse order
}
// Enqueue left and right children
if (node.left !== null) {
queue.push(node.left);
}
if (node.right !== null) {
queue.push(node.right);
}
}
result.push(currentLevel); // Add the current level's values to the result array
leftToRight = !leftToRight; // Toggle the direction for the next level
}
return result;
};
51.33MB, 46ms
