二叉树遍历基础与递归、迭代解法详解

二叉树的前序、中序、后序和层序遍历是数据结构和算法中常见的操作，对于理解二叉树的结构至关重要。这些遍历方式在LeetCode的144、94、145和102题中被考察，涉及递归、迭代、栈和队列等多种方法。 1. 前序遍历 - 题目描述：要求按照根节点 -> 左子树 -> 右子树的顺序访问二叉树的所有节点。 - 题目分析：递归是最直观的理解方法，通过函数调用自身处理左右子树，但要实现迭代，需要借助栈来模拟递归过程。栈的作用在于先压入根节点，然后依次弹出并访问节点，再将剩余未访问的子树压入栈中。 - Python实现（递归）： ```python class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: if not root: return [] return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right) ``` - Python实现（迭代，栈）： ```python class Solution: def preorderTraversal(self, root): stack, res = [root], [] while stack: node = stack.pop() if node: res.append(node.val) stack.extend([node.right, node.left]) else: continue return res ``` 2. 中序遍历 - 中序遍历顺序是左子树 -> 根节点 -> 右子树。 - 迭代实现类似前序遍历，只是调整栈的压入顺序，先左子树，后根节点。 3. 后序遍历 - 后序遍历顺序是左子树 -> 右子树 -> 根节点。 - 这里同样需要使用栈来辅助，但与前序不同的是，要先处理完左右子树后再访问根节点。 4. 层序遍历 - 层次遍历按照树的层级顺序逐层访问，通常使用队列来实现。首先将根节点放入队列，然后取出节点访问，再将其左右子节点（如果存在）加入队列，直到队列为空。 掌握这些基本遍历方法有助于深入理解二叉树的数据结构，并且在实际编程中处理各种复杂的树形问题时非常有用。在实际项目中，递归虽然直观，但在面对大数据量或性能要求高的场景时，迭代方法通常更高效。同时，理解和使用栈和队列作为数据结构也是算法设计的重要环节。