二叉树前中后序遍历详解
一、二叉树的前序遍历
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. 迭代写法
迭代法利用栈来模拟递归过程。由于栈是'后进先出'，为了保持'根→左→右'的顺序，我们需要调整入栈顺序。
核心逻辑：
- 初始化栈，将根节点压入。
- 当栈不为空时，弹出栈顶节点并访问。
- 关键点：先将右子树入栈，再将左子树入栈。这样弹出时左子树会先被处理。
代码实现：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
list.add(node.val);
// 注意入栈顺序：先右后左
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return list;
}
}
解析： 此方法避免了递归的栈溢出风险。实际运行中，入栈顺序决定了出栈顺序，务必记住'右先左后'这一细节。
二、二叉树的中序遍历
1. 递归写法
中序遍历顺序为'左子树 → 根节点 → 右子树'。
代码实现：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
inOrder(root, list);
return list;
}
private void inOrder(TreeNode root, List<Integer> list) {
if (root == null) return;
inOrder(root.left, list); // 先左
list.add(root.val); // 再根
inOrder(root.right, list); // 后右
}
}
2. 迭代写法
迭代的核心在于'一路向左'，直到无法继续，然后回溯访问根节点，再转向右子树。
核心逻辑：
- 使用指针
curr指向当前节点。 - 只要
curr不为空或栈非空：- 若
curr不为空，将其压栈并向左移动。 - 若
curr为空，说明左侧已到底，弹出栈顶（即最近的一个祖先），访问它，然后转向其右子树。
- 若
代码实现：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
list.add(curr.val);
curr = curr.right;
}
return list;
}
}
三、二叉树的后序遍历
后序遍历顺序为'左子树 → 右子树 → 根节点'。这是三种遍历中最难用迭代实现的，因为根节点最后访问，需要区分何时可以安全地访问根节点。
1. 递归写法
代码实现：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
postOrder(root, list);
return list;
}
private void postOrder(TreeNode root, List<Integer> list) {
if (root == null) return;
postOrder(root.left, list); // 先左
postOrder(root.right, list); // 再右
list.add(root.val); // 最后根
}
}
2. 迭代写法 1：双指针标记法
通过记录上一个访问的节点 pre，判断当前节点的右子树是否已处理完毕。
核心逻辑：
- 遍历到最左节点入栈。
- 检查栈顶节点的右子树：如果为空或已被访问过，则弹出并访问当前节点；否则转向右子树。
代码实现：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;
Deque<TreeNode> stack = new LinkedList<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
TreeNode node = stack.peek();
// 若右子树为空或已访问，则可访问根节点
if (node.right == null || node.right == pre) {
list.add(stack.pop().val);
pre = node;
root = null;
} else {
root = node.right;
}
}
return list;
}
}
3. 迭代写法 2：前序变形 + 翻转
利用前序遍历'根→左→右'与后序遍历'左→右→根'的关系。如果我们修改前序遍历为'根→右→左'，得到的结果反转后即为后序遍历。
核心逻辑：
- 按'根→右→左'顺序遍历（先入右子树，再入左子树）。
- 遍历结束后，将结果列表反转。
代码实现：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
list.add(node.val);
// 注意入栈顺序：先左后右，保证弹出时先右后左
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
Collections.reverse(list);
return list;
}
}
总结：
- 递归写法代码量少，易于理解，但受限于系统栈深度。
- 迭代写法更稳健，适合对性能要求高或树结构极深的场景。
- 后序遍历的迭代实现中，'翻转法'通常比'双指针法'更易编写且不易出错。