Level Order Traversal

# Level Order Traversal ## Difficulty Medium ## Tags `tree`, `bfs`, `queue` ## Problem Statement Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level). ## Constraints - The number of nodes in the tree is in the range [0, 2000]. - -1000 ≤ Node.val ≤ 1000 - Return a list of lists, where each inner list contains the values at one level. ## Signatures ### Python ```python def level_order(root: TreeNode) -> List[List[int]]: pass ``` ### Java ```java public class Solution { public List<List<Integer>> level_order(TreeNode root) { return null; } } ``` ### Csharp ```csharp public class Solution { public IList<IList<int>> level_order(TreeNode root) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: vector<vector<int>> level_order(TreeNode* root) { } }; ``` ### C ```c vector<int*> level_order(TreeNode* root) { } ``` ### Ruby ```ruby def level_order(root) end ``` ### Perl ```perl sub level_order { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def level_order(root: TreeNode): List[List[Int]] = { } } ``` ### Haskell ```haskell level_order :: ... -> ... level_order args = undefined ``` ### Clojure ```clojure (defn level_order [root] ) ``` ### Scheme ```scheme (define (level_order root) ) ``` ## Examples ### Example 1 **Input:** ``` 3 / \ 9 20 / \ 15 7 ``` **Output:** ``` [[3], [9, 20], [15, 7]] ``` **Explanation:** - Level 0: [3] - Level 1: [9, 20] - Level 2: [15, 7] ### Example 2 **Input:** ``` root = [1] ``` **Output:** ``` [[1]] ``` ### Example 3 **Input:** ``` root = [] ``` **Output:** ``` [] ``` ## Hints 1. Use Breadth-First Search (BFS) with a queue. 2. At the start of each level, record the queue size. 3. Process exactly that many nodes to complete the current level. 4. Add each processed node's children to the queue for the next level.