Binary Tree Level Order Traversal Leetcode

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:
Input: root = [3,9,20,null,null,15,7] 
Output: [[3],[9,20],[15,7]]

Example 2:
Input: root = [1]
Output: [[1]]

Example 3:
Input: root = []
Output: []

Binary Tree Level Order Traversal Python Solution

class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []
        Q = deque([root])
        levels = [[root.val]]
        temp = deque()
        while Q:
            node = Q.popleft()
            if node.left: temp.append(node.left)
            if node.right: temp.append(node.right)
            if not Q:
                if temp:
                    levels.append([n.val for n in temp])
                Q = temp
                temp = deque()
        return levels

Coding Pattern Used in this Solution

The coding pattern used in all the provided implementations is Tree Breadth-First Search (BFS).
This pattern commonly traverses a tree level by level, processing all nodes at the current depth before moving to the next depth.
BFS is implemented using a queue data structure to keep track of nodes at each level.

Time and Space Complexity for this Solution

1. The Time complexity is O(N) because each node is visited once.
2. The Space complexity is O(M) because the queue (or recursion stack) holds up to the maximum number of nodes at any level.

Reference:

1. LeetCode Problem
2. LeetCode Soluton
3. Breadth-First Search

The above is the detailed content of Binary Tree Level Order Traversal Leetcode. For more information, please follow other related articles on the PHP Chinese website!