代码随想录算法训练营第17期第15天 | 层序遍历 、递归遍历、迭代遍历、统一迭代

**代码随想录算法训练营第17期第15天**

今天，我们将讨论四种不同的树遍历方法：层序遍历（BFS）、递归遍历、迭代遍历和统一迭代。这些方法都是用于遍历二叉树或其他数据结构的重要工具。

### 层序遍历（BFS）

层序遍历是从根节点开始，按照从左到右的顺序访问每个节点，然后再访问下一层的所有节点。这种方法适合于需要按层次访问树中的元素的情况。

from collections import dequeclass TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef bfs(root):
 if not root:
 return []
 result = []
 queue = deque([root])
 while queue:
 level_size = len(queue)
 current_level = []
 for _ in range(level_size):
 node = queue.popleft()
 current_level.append(node.val)
 if node.left:
 queue.append(node.left)
 if node.right:
 queue.append(node.right)
 result.append(current_level)
 return result

def dfs(root):
 if not root:
 return []
 result = []
 def traverse(node, level):
 if node is None:
 return if len(result) <= level:
 result.append([])
 result[level].append(node.val)
 traverse(node.left, level +1)
 traverse(node.right, level +1)
 traverse(root,0)
 return result

def dfs_iterative(root):
 if not root:
 return []
 result = []
 stack = [(root,0)]
 while stack:
 node, level = stack.pop()
 if len(result) <= level:
 result.append([])
 result[level].append(node.val)
 if node.right:
 stack.append((node.right, level +1))
 if node.left:
 stack.append((node.left, level +1))
 return result

def unified_iterative(root):
 if not root:
 return []
 result = []
 stack = [(root,0)]
 queue = deque([root])
 while stack or queue:
 if stack:
 node, level = stack.pop()
 if len(result) <= level:
 result.append([])
 result[level].append(node.val)
 if node.right:
 stack.append((node.right, level +1))
 if node.left:
 stack.append((node.left, level +1))
 else:
 level_size = len(queue)
 current_level = []
 for _ in range(level_size):
 node = queue.popleft()
 current_level.append(node.val)
 if node.left:
 queue.append(node.left)
 if node.right:
 queue.append(node.right)
 result.append(current_level)
 return result