二叉树层次顺序遍历 Leetcode

给定二叉树的根，返回其节点值的级别顺序遍历。 （即从左到右，逐级）。

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: []

二叉树层次顺序遍历Python解决方案

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

本解决方案中使用的编码模式

所有提供的实现中使用的编码模式是树广度优先搜索（BFS）。
此模式通常逐层遍历树，在移动到下一个深度之前处理当前深度的所有节点。
BFS 使用队列数据结构来实现，以跟踪每个级别的节点。

该解决方案的时间和空间复杂度

1. 时间复杂度为 O(N)，因为每个节点都被访问一次。
2. 空间复杂度为 O(M)，因为队列（或递归堆栈）在任何级别都能容纳最大数量的节点。

参考：

1. LeetCode 问题
2. LeetCode 解决方案
3. 广度优先搜索

以上是二叉树层次顺序遍历 Leetcode的详细内容。更多信息请关注PHP中文网其他相关文章！