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

故事背景

假设你在一座有多个房间的房子里探险，每个房间都有一个号码。有的房间有两个门，分别通往左边的房间和右边的房间。你的任务是按照一定的顺序记录下每个房间的号码。这种顺序叫做“后序遍历”。

游戏规则

后序遍历的规则很简单：

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

示例

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

示例 1

假设房子是这样的：

    1
     \
      2
     /
    3

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

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

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

示例代码

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

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

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

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

public class BinaryTreePostorderTraversal {

    /**
     * 后序遍历
     * @param root 二叉树的根节点
     * @return 节点值的后序遍历结果（作为 int[] 数组）
     */
    public int[] postorderTraversal(TreeNode root) {
        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);

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

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

解释

1. 定义二叉树节点：
1. 使用 TreeNode 类来表示二叉树的节点，每个节点包含一个值 val 和两个指向左右孩子的指针 left 和 right。
2. 后序遍历方法：
1. postorderTraversal 方法接收一个 TreeNode 类型的参数 root，表示二叉树的根节点。
2. 使用一个 ArrayList 类型的列表 result 来存储遍历的结果。
3. 辅助遍历方法：
1. traverse 方法用于递归地遍历二叉树。
2. 如果当前节点为空，直接返回。
3. 先递归遍历当前节点的左子树。
4. 再递归遍历当前节点的右子树。
5. 最后访问当前节点，将其值添加到结果列表中。

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