python二叉树遍历顺序

### Python 二叉树不同遍历方法实现 #### 定义二叉树结构 为了更好地理解各种遍历方式，在这里先定义一个简单的二叉树类。 ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right ``` #### 前序遍历 (Pre-order Traversal) 前序遍历遵循根节点 -> 左子树 -> 右子树 的顺序。可以采用迭代法利用栈来模拟这个过程[^1]。 ```python def preorderTraversal(root): stack, result = [], [] current = root while stack or current: if current: result.append(current.val) # 访问当前节点 stack.append(current) current = current.left # 移动到左孩子 else: node = stack.pop() current = node.right # 转向处理右孩子 return result ``` #### 中序遍历 (In-order Traversal) 中序遍历按照左子树 -> 根节点 -> 右子树 来访问各个节点，同样可以通过栈来进行非递归版本的实现。 ```python def inorderTraversal(root): stack, result = [], [] current = root while stack or current: if current is not None: stack.append(current) current = current.left # 不断深入左侧分支直到尽头 else: node = stack.pop() # 开始回溯并记录路径上的值 result.append(node.val) current = node.right # 处理右侧部分 return result ``` #### 后序遍历 (Post-order Traversal) 对于后序遍历来说，则是以左子树 -> 右子树 -> 根节点 这样的模式展开操作。由于最后才访问父节点，因此需要额外注意如何标记已经完成两侧子树的操作。 ```python def postorderTraversal(root): stack, output = [root], [] while stack: node = stack.pop() if node is not None: output.append(node.val) # Push children to the stack in reverse order of desired traversal. stack.append(node.left) stack.append(node.right) return list(reversed(output)) ``` #### 层次遍历 (Level Order Traversal) 层次遍历是从上至下逐层扫描整棵树中的每一个元素，并按从左往右排列输出同一层内的所有数据项。通常借助队列这种先进先出的数据结构辅助完成任务[^2]。 ```python from collections import deque def levelOrder(root): queue, results = deque([root]), [] while queue: level_length = len(queue) for _ in range(level_length): node = queue.popleft() if node: results.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return results ``` 上述四种遍历算法分别展示了不同的访问策略以及相应的代码实现方式。每种遍历都有其特点和应用场景，选择合适的遍历取决于具体需求。