层次遍历二叉树

层次遍历（也称为广度优先遍历）是一种用于遍历或搜索树形结构的方法。对于二叉树而言，它按照从上到下、从左到右的顺序访问节点，依次打印出每一层的所有节点。这种遍历方式在许多应用场景中非常有用，如图像处理、网格搜索等。

什么是层次遍历？

层次遍历的基本思想是首先将根节点加入队列（或其他数据结构），然后逐个取出队列中的元素进行处理，并将该节点的子节点按照从左到右的顺序依次添加进队列。这个过程一直持续到队列为空，即所有节点都被访问过了。

层次遍历二叉树的方法

实现层次遍历通常有两种方法：使用队列和递归。下面分别介绍这两种方法的具体步骤：

使用队列

初始化：创建一个队列，并将根节点加入队列。
循环处理：从队列中取出节点，访问该节点（如打印其值），然后将其左右子节点依次按顺序加入队列。重复这一过程直到队列为空。

def level_order(root):
    if root is None:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        current_node = queue.pop(0)
        result.append(current_node.val)
        
        if current_node.left:
            queue.append(current_node.left)
        if current_node.right:
            queue.append(current_node.right)
            
    return result

递归方法

递归方法更直观，但可能会使用更多的栈空间（取决于树的高度）。

定义函数：创建一个辅助函数，该函数接受当前节点和层数作为参数。
遍历节点：如果当前节点不为空，则访问它，并根据其深度调整结果列表的位置。

def level_order_recursive(root):
    def helper(node, level):
        if not node:
            return
        
        if len(result) == level:
            result.append([])
            
        result[level].append(node.val)
        
        if node.left:
            helper(node.left, level + 1)
        if node.right:
            helper(node.right, level + 1)
    
    result = []
    helper(root, 0)
    return result

应用场景

层次遍历在图像处理中非常有用，例如在绘制图形时可以确保所有像素都被按正确的顺序处理。此外，在社交网络分析中，它可以用来找到所有好友的层级关系。

总结

层次遍历二叉树是一种有效的算法，广泛应用于各种需要按照层级结构访问节点的应用场景中。通过队列或递归方法实现，这种方法不仅简单易懂，而且能够确保正确处理树形结构中的每个节点。