Given the root of a binary tree, return its node values level by level: a list whose first element holds the root's value, the second holds the values on depth 1 from left to right, and so on.
- The number of nodes is in the range 0 to 2000
- -1000 <= Node.val <= 1000
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
One simple approach is DFS that passes the depth along and appends each value to res[depth]; it works but hides the idea interviewers look for. BFS with a queue naturally processes nodes in level order. The trick is to snapshot len(queue) at the start of every round: exactly that many nodes belong to the current level, and everything pushed while processing them belongs to the next level.
Algorithm
- If
rootis null, return[]. Putrootin a queue. - While the queue is not empty, let
size = len(queue)and create an emptylevellist. - Pop
sizenodes, append each value tolevel, and push its non-null children. - Append
levelto the answer.
O(n)Space: O(w), where w is the maximum width of the treeclass Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] res = [] queue = deque([root]) while queue: level = [] for _ in range(len(queue)): # nodes on the current level node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res