94.二叉树的中序遍历
94. 二叉树的中序遍历
题意
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
难度
简单
示例
示例 1：
094.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%AD%E5%BA%8F%E
9%81%8D%E5%8E%86-20231029150551.png
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
分析
对于这道题，我们需要先搞清楚，什么是二叉树的中序遍历。
前序遍历、中序遍历、后序遍历是二叉树的三种基本遍历方式，它们的主要区别在于访问
根节点的时间。
1. 前序遍历 (Preorder Traversal)
– 先访问根节点
– 接着访问左子树
– 最后访问右子树
– 遍历顺序：根 -> 左 -> 右
2. 中序遍历 (Inorder Traversal)
– 先访问左子树
– 接着访问根节点
– 最后访问右子树
– 遍历顺序：左 -> 根 -> 右
3. 后序遍历 (Postorder Traversal)
– 先访问左子树
– 接着访问右子树
– 最后访问根节点
– 遍历顺序：左 -> 右 -> 根
这里是一个简单的二叉树示意图：
A
/
B C
//
D EF G
对于这个二叉树：
• 前序遍历的结果是：A, B, D, E, C, F, G
• 中序遍历的结果是：D, B, E, A, F, C, G
• 后序遍历的结果是：D, E, B, F, G, C, A
我们可以写出一个中序遍历大概的算法雏形
public void traversal(TreeNode node) {
if (node.left != null) {
traversal(node.left);
}
read(node);
if (node.right != null) {
traversal(node.right);
}
}
同理我们稍微变换一下也可以得到对应的前序和后序遍历的算法
public void traversal(TreeNode node) {
read(node);
if (node.left != null) {
traversal(node.left);
}
if (node.right != null) {
traversal(node.right);
}
}
public void traversal(TreeNode node) {
if (node.left != null) {
traversal(node.left);
}
if (node.right != null) {
traversal(node.right);
}
read(node);
}
最后我们只需要稍微对边界条件进行限制即可得到最终的算法。
/**
* 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 {
// 创建一个列表，用于存放中序遍历的结果
List<Integer> res = new ArrayList<>();
// 主方法，开始中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
// 如果树不为空，则开始遍历
if (root != null) {
traversal(root);
}
// 返回中序遍历的结果
return res;
}
// 读取当前节点的值，并将其添加到结果列表中
public void read(TreeNode node) {
res.add(node.val);
}
// 中序遍历的核心逻辑
public void traversal(TreeNode node) {
// 如果当前节点的左子树不为空，先遍历左子树
if (node.left != null) {
traversal(node.left);
}
// 访问当前节点
read(node);
// 如果当前节点的右子树不为空，接着遍历右子树
if (node.right != null) {
traversal(node.right);
}
}
}
当输入为 1,null,2,3，二叉树可以表示为以下结构：
1
2
/
3
我们来模拟一下题解中的中序遍历过程。
1. 初始调用：从根节点 1 开始调用 inorderTraversal。
2. 在 inorderTraversal 中，检查根节点 1 是否为 null。既然不是，继续调用
traversal。
3. 在 traversal 中：
– 先检查节点 1 的左子树是否存在。但节点 1 的左子树是 null，所以不做进一步
递归。
– 然后，调用 read 方法访问节点 1 并将值 1 添加到结果列表 res 中。
– 接着，它会遍历节点 1 的右子树，即节点 2。
4. 为节点 2 重复步骤 3：
– 先检查节点 2 的左子树。这里，节点 2 有一个左子节点 3，所以它递归调用
traversal 为节点 3。
–对于节点 3，它没有左子树，所以它直接访问该节点，并将值 3 添加到结果列
表 res 中。
– 节点 3 没有右子树，所以没有进一步的递归调用。
– 回到节点 2，在访问了它的左子树后，现在访问节点 2 本身，并将值 2 添加到
结果列表 res 中。
– 节点 2 没有右子树，所以此处的遍历结束。
5. 在完成以上所有步骤后，遍历完成。
根据以上描述，结果列表 res 为：[1, 3, 2]。
来看一下题解效率：
094.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%AD%E5%BA%8F%E
9%81%8D%E5%8E%86-20231029152213.png
总结
递归处理是处理树形结构中最常用的一个操作，因为树的结构本质与递归殊途同归，在逻
辑结构上二者十分近似，所以在学习树结构时，我们通常都可以类比递归，并从中获得启
发。
力扣链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/