二叉树层序遍历递归python递归层次遍历二叉树

介绍

在数据结构中，树是最常用的一种基本数据结构。其操作和特性可以应用在各种领域，例如编译器技术、操作系统、网络协议等等。二叉树是一种特殊的树，它有如下特点：每个节点最多有两个子节点（left和right），如果有子节点则子节点排列顺序是有序的。

二叉树层序遍历递归python

层序遍历二叉树就是从上到下一层一层输出树中的节点。递归实现层序遍历一般使用dfs遍历，定义一个字典记录每个深度节点，dfs遍历过程中记录当前深度，将节点加入当前深度的列表中即可。

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        def dfs(root, level):
            if not root: return
            if len(res) == level: res.append([])
            res[level].append(root.val)
            dfs(root.left, level + 1)
            dfs(root.right, level + 1)
        dfs(root, 0)
        return res

递归层次遍历二叉树

层次遍历一般基于队列实现，因为先进先出的特性。使用队列实现层次遍历时，我们需要记录每个节点的深度，以便将节点插入到相应深度的列表中。如果未记录深度，将难以插入到相应的层次中。

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        level = 0
        queue = [(root, 0)]
        while queue:
            node, lv = queue.pop(0)
            if node:
                if len(res) == lv: res.append([])
                res[lv].append(node.val)
                queue.append((node.left, lv+1))
                queue.append((node.right, lv+1))
        return res

代码示例

下面是一个完整的二叉树层序遍历递归和队列实现的示例代码。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        level = 0
        queue = [(root, 0)]
        while queue:
            node, lv = queue.pop(0)
            if node:
                if len(res) == lv: res.append([])
                res[lv].append(node.val)
                queue.append((node.left, lv+1))
                queue.append((node.right, lv+1))
        return res
    
    def levelOrder_recursive(self, root: TreeNode) -> List[List[int]]:
        res = []
        def dfs(root, level):
            if not root: return
            if len(res) == level: res.append([])
            res[level].append(root.val)
            dfs(root.left, level + 1)
            dfs(root.right, level + 1)
        dfs(root, 0)
        return res

总结

二叉树是一种重要的基础数据结构，在很多应用中都有广泛的应用。其中层次遍历是常用的遍历方式，在二叉树中应用广泛。递归和队列都能够实现层次遍历。使用递归实现层次遍历需要记录每个节点深度，而使用队列则要记录深度和节点，从而能够将节点顺序插入到相应的层次中。在实际应用中，根据情况选择不同的方法实现层次遍历。