Question
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).
Example 1:
1 2
| Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]
|
Example 2:
1 2
| Input: root = [1] Output: [[1]]
|
Example 3:
1 2
| Input: root = [] Output: []
|
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> q = new LinkedList<>(); if(root != null) q.offer(root); while(!q.isEmpty()){ int size = q.size(); List<Integer> level = new ArrayList<>(); for(int i = 0; i < size; i++){ TreeNode cur = q.poll(); level.add(cur.val); if(cur.left != null) q.offer(cur.left); if(cur.right != null) q.offer(cur.right); } res.add(level); } return res; } }
|
Complexity:
Time complexity: O(n)
Space complexity: O(n)