102. Binary Tree Level Order Traversal
給定一個二元樹的根節點，返回其節點值的層次遍歷。即從左到右、一層層地遍歷。
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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return [] # Return an empty list if the root is None
result = []
queue = deque([root]) # Initialize the queue with the root node
while queue:
level_size = len(queue) # Get the number of elements at the current level
level = []
for _ in range(level_size): # Process each node at the current level
node = queue.popleft() # Dequeue the leftmost element
level.append(node.val) # Append its value to the level list
# Enqueue left and right children if they exist
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level) # Add the completed level to the result list
return result
17.09MB, 43ms
C++
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result; // Return empty result for null root
queue<TreeNode*> queue;
queue.push(root); // Start with the root
while (!queue.empty()) {
int levelSize = queue.size(); // Number of elements in the current level
vector<int> level; // Vector to store the current level's values
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = queue.front(); // Get the front node
queue.pop(); // Remove the node from the queue
level.push_back(node->val); // Add the node's value to the current level
if (node->left) queue.push(node->left); // Add left child to the queue if it exists
if (node->right) queue.push(node->right); // Add right child to the queue if it exists
}
result.push_back(level); // Add the completed level to the result
}
return result;
}
};
14.96MB, 3ms
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 levelOrder = function(root) {
if (!root) return []; // If the root is null, return an empty array
const result = [];
const queue = []; // Using an array to simulate a queue for BFS
queue.push(root); // Start with the root node
while (queue.length > 0) {
const levelSize = queue.length; // Number of elements at the current level
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
currentLevel.push(node.val); // Collect its value
if (node.left !== null) {
queue.push(node.left); // Enqueue left child
}
if (node.right !== null) {
queue.push(node.right); // Enqueue right child
}
}
result.push(currentLevel); // Add the current level's values to the result array
}
return result; // Return the level-by-level order traversal
};
54.02MB, 69ms
