二叉树前中后序遍历详解
二叉树是数据结构中的核心结构之一，其遍历方式是理解树形算法的基础。本文将深入解析前序、中序、后序三种遍历模式，分别展示递归与迭代的实现细节，并对比不同方案的优劣。
一、二叉树的前序遍历
前序遍历遵循「根节点 → 左子树 → 右子树」的访问顺序。
1. 递归写法
递归是最直观的解法，直接映射遍历定义。核心在于先处理当前节点，再依次递归左右子树。
实现逻辑：
- 终止条件：节点为空时返回。
- 访问当前：将节点值加入结果列表。
- 递归左子树：继续向左深入。
- 递归右子树：最后处理右侧分支。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
find(root);
return list;
}
private void find(TreeNode node) {
if (node != null) {
list.add(node.val);
find(node.left);
find(node.right);
}
}
}
时间复杂度为 O(n)，空间复杂度取决于递归栈深度，最坏为 O(n)。
2. 迭代写法
迭代法利用栈模拟系统调用栈。由于栈是后进先出（LIFO），为了优先访问左子树，我们需要先将右子树入栈，再将左子树入栈。
关键步骤：
- 初始化栈，将根节点压入。
- 循环弹出栈顶节点，记录值。
- 先压入右子节点，再压入左子节点。
- 重复直至栈空。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
(root == ) list;
Deque<TreeNode> stack = <>();
stack.push(root);
(!stack.isEmpty()) {
stack.pop();
(node == ) ;
list.add(node.val);
stack.push(node.right);
stack.push(node.left);
}
list;
}
}
