二叉树遍历：LeetCode 144 / 94 / 145 之递归 + 分治 + 非递归

🏠个人主页：得鹿梦鱼 🎬作者简介：C/C++/JAVA后端开发学习者 ❄️个人专栏：C语言、数据结构（C语言）、EasyX ❄️个人专栏：JAVA SE、数据结构与算法（JAVA） ❄️个人专栏：游戏、规划、程序人生 ✨ 从来绝巘须孤往，万里同尘即玉京

文章目录

• • @[TOC] 
• 🌳二叉树遍历：LeetCode 144 / 94 / 145 之递归 + 分治 + 非递归
• • 📝 文章说明
• 一、二叉树的前序遍历（LeetCode 144）
• • 1. 思路一：遍历思想
  • 2. 思路二：分治思想
  • 3. 思路三：非递归（栈模拟法）
• 二、二叉树的中序遍历（LeetCode 94）
• • 1. 思路一：遍历思想
  • 2. 思路二：分治思想
  • 3. 思路三：非递归（栈模拟法）
• 三、二叉树的后序遍历（LeetCode 145）
• • 1. 思路一：遍历思想
  • 2. 思路二：分治思想
  • 3. 思路三：非递归（栈模拟法）
• 🎯 核心总结
• ✍️ 写在最后

🌳二叉树遍历：LeetCode 144 / 94 / 145 之递归 + 分治 + 非递归

📝 文章说明

本文针对二叉树前序、中序、后序遍历三大核心题型，提供三种通用解题思路：

所有代码均可直接提交 LeetCode，层次清晰、易学易记。

一、二叉树的前序遍历（LeetCode 144）

给你二叉树的根节点 root，返回它节点值的前序遍历。 遍历规则：根 → 左 → 右

1. 思路一：遍历思想

• 思路：递归遍历整棵树，边遍历边记录结果
• 代码实现

class Solution {
public List<Integer> result = new ArrayList<>();

public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return result;
}
// 根
result.add(root.val);
// 左
preorderTraversal(root.left);
// 右
preorderTraversal(root.right);
return result;
}
}

2. 思路二：分治思想

• 思路：把问题拆分，先处理左子树、再处理右子树，最后合并结果
• 代码实现

class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
// 根
result.add(root.val);
// 左子树结果
List<Integer> leftResult = preorderTraversal(root.left);
result.addAll(leftResult);
// 右子树结果
List<Integer> rightResult = preorderTraversal(root.right);
result.addAll(rightResult);

return result;
}
}

3. 思路三：非递归（栈模拟法）

• 思路：利用栈模拟递归，右先入栈、左后入栈，保证左先执行
• 代码实现

class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}

Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);

while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);

// 右先入栈
if (node.right != null) {
stack.push(node.right);
}
// 左后入栈
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}
}

二、二叉树的中序遍历（LeetCode 94）

给你二叉树的根节点 root，返回它节点值的中序遍历。 遍历规则：左 → 根 → 右

1. 思路一：遍历思想

• 思路：递归走到最左，回溯时记录根节点，再进入右子树
• 代码实现

class Solution {
public List<Integer> result = new ArrayList<>();

public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return result;
}
// 左
inorderTraversal(root.left);
// 根
result.add(root.val);
// 右
inorderTraversal(root.right);
return result;
}
}

2. 思路二：分治思想

• 思路：先拿到左子树结果 → 加入根 → 加入右子树结果
• 代码实现

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
// 左
List<Integer> leftResult = inorderTraversal(root.left);
result.addAll(leftResult);

// 根
result.add(root.val);

// 右
List<Integer> rightResult = inorderTraversal(root.right);
result.addAll(rightResult);

return result;
}
}

3. 思路三：非递归（栈模拟法）

• 思路： ① 一路向左，全部入栈 ② 出栈时访问 ③ 转向右子树
• 代码实现

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}

Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;

while (cur != null || !stack.isEmpty()) {
if (cur != null) {
// 一路向左
stack.push(cur);
cur = cur.left;
} else {
// 出栈 + 访问
cur = stack.pop();
result.add(cur.val);
// 向右
cur = cur.right;
}
}
return result;
}
}

三、二叉树的后序遍历（LeetCode 145）

给你二叉树的根节点 root，返回它节点值的后序遍历。 遍历规则：左 → 右 → 根

1. 思路一：遍历思想

• 思路：先遍历左、再遍历右，最后记录根节点
• 代码实现

class Solution {
public List<Integer> result = new ArrayList<>();

public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return result;
}
// 左
postorderTraversal(root.left);
// 右
postorderTraversal(root.right);
// 根
result.add(root.val);
return result;
}
}

2. 思路二：分治思想

• 思路：合并左、右结果，最后加入根节点
• 代码实现

class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
// 左
List<Integer> leftResult = postorderTraversal(root.left);
result.addAll(leftResult);
// 右
List<Integer> rightResult = postorderTraversal(root.right);
result.addAll(rightResult);
// 根
result.add(root.val);

return result;
}
}

3. 思路三：非递归（栈模拟法）

• 思路：前序（根 → 左 → 右） → 改为（根 → 右 → 左） → 最后反转得到后序
• 代码实现

class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}

Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);

while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);

// 左先入栈
if (node.left != null) {
stack.push(node.left);
}
// 右后入栈
if (node.right != null) {
stack.push(node.right);
}
}
// 反转：根 → 右 → 左 → 左 → 右 → 根
Collections.reverse(result);
return result;
}
}

🎯 核心总结

通用技巧：

• 递归最简单，适合快速写题
• 分治思想适合理解二叉树结构
• 非递归用栈，面试高频考点

✍️ 写在最后

这三篇遍历是二叉树所有题目的基础骨架。 掌握这三种写法，二叉树的绝大多数题目都能轻松上手。 下一篇：层序遍历、对称二叉树、翻转二叉树、路径总和等高频真题。