题解 | #二叉树的中序遍历#

故事背景

想象你在一个迷宫里探险，这个迷宫是由许多房间组成的。每个房间都有一个号码，有的房间有两个门，分别通往左边的房间和右边的房间。你的任务是按照一定的顺序记录下每个房间的号码。这种顺序叫做“中序遍历”。

游戏规则

中序遍历的规则很简单：

1. 先去看看左边的房间（如果有的话）。
2. 然后记下当前房间的号码。
3. 再去看看右边的房间（如果有的话）。

示例

让我们通过一个简单的例子来理解这个过程：

示例 1

假设迷宫是这样的：

    1
   / \
  2   3

按照中序遍历的规则，我们应该这样记录：

1. 先去看看 1 的左孩子 2。
2. 然后记下 2 的号码。
3. 回到 1，记下 1 的号码。
4. 再去看看 1 的右孩子 3。
5. 最后记下 3 的号码。

最终的结果应该是：[2, 1, 3]

示例代码

现在我们用Java来实现这个过程：

import java.util.ArrayList;
import java.util.List;

// 定义二叉树节点
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreeInorderTraversal {

    /**
     * 中序遍历
     * @param root 二叉树的根节点
     * @return 节点值的中序遍历结果（作为 int[] 数组）
     */
    public int[] inorderTraversal(TreeNode root) {
        if(root = null){
			return new int[0];
		}
        List<Integer> result = new ArrayList<>();
        traverse(root, result);
        
        // 将 List 转换为 int[] 数组
        int[] resultArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }
        
        return resultArray;
    }

    /**
     * 辅助方法，用于递归遍历
     * @param node 当前节点
     * @param list 用于存储结果的列表
     */
    private void traverse(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }

        // 先去看看左边的房间
        traverse(node.left, list);

        // 然后记下当前房间的号码
        list.add(node.val);

        // 再去看看右边的房间
        traverse(node.right, list);
    }

}

解释

1. 定义二叉树节点：
1. 使用 TreeNode 类来表示二叉树的节点，每个节点包含一个值 val 和两个指向左右孩子的指针 left 和 right。
2. 中序遍历方法：
1. inorderTraversal 方法接收一个 TreeNode 类型的参数 root，表示二叉树的根节点。
2. 使用一个 ArrayList 类型的列表 result 来存储遍历的结果。
3. 辅助遍历方法：
1. traverse 方法用于递归地遍历二叉树。
2. 如果当前节点为空，直接返回。先递归遍历当前节点的左子树。
3. 访问当前节点，将其值添加到结果列表中。
4. 最后递归遍历当前节点的右子树。
4. 主方法：
1. 在 main 方法中创建了几个示例二叉树，并调用 inorderTraversal 方法获取结果。
2. 使用 Arrays.toString 方法将 int[] 数组转换为字符串表示形式，便于输出查看。

测试结果

对于每个示例：

• 示例 1：[2, 1, 3]
• 示例 2：[]
• 示例 3：[2, 1]
• 示例 4：[1, 2]

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。