如何将前序生成的Java节点列表转为后序遍历？

核心规则梳理 #

先明确你描述的节点与遍历规则：

• 每个节点包含leftName和rightName字段
• 若leftName为null → 节点存在左子树；若rightName为null → 节点存在右子树；两者均为null → 节点有左右两个子树（对应后续的两个叶子节点）
• 若leftName和rightName均不为null → 节点是叶子，遍历输出这两个字段
• 输入为前序遍历生成的节点列表（根→左子树→右子树），目标是输出后序遍历结果（左子树→右子树→当前节点的非null字段）

关键解决思路 #

你的核心痛点是无法确定左子树的结束索引，这里可以通过递归计算子树节点数量的方式动态划分范围：

1. 递归函数处理当前节点时，先判断是否为叶子节点
2. 若非叶子节点，先递归处理左子树，获取左子树处理完成后的下一个节点索引（即右子树的起始索引）
3. 再基于该索引递归处理右子树
4. 最后处理当前节点的非null字段输出

Java代码实现 #

首先定义节点类：

class Node {
    String leftName;
    String rightName;

    public Node(String leftName, String rightName) {
        this.leftName = leftName;
        this.rightName = rightName;
    }
}

然后实现转换逻辑：

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

public class TreeTraversalConverter {

    // 对外暴露的转换方法
    public List<String> convertPreorderToPostorder(List<Node> preorderList) {
        List<String> postorderResult = new ArrayList<>();
        if (preorderList == null || preorderList.isEmpty()) {
            return postorderResult;
        }
        traverse(preorderList, 0, postorderResult);
        return postorderResult;
    }

    // 递归遍历核心方法，返回处理完当前子树后的下一个节点索引
    private int traverse(List<Node> preorderList, int startIndex, List<String> result) {
        if (startIndex >= preorderList.size()) {
            return startIndex;
        }

        Node currentNode = preorderList.get(startIndex);

        // 叶子节点：直接输出两个字段，返回下一个节点索引
        if (currentNode.leftName != null && currentNode.rightName != null) {
            result.add(currentNode.leftName);
            result.add(currentNode.rightName);
            return startIndex + 1;
        }

        int nextIndex = startIndex;

        // 处理左子树：leftName为null则递归遍历左子树，否则直接输出非null值
        if (currentNode.leftName == null) {
            nextIndex = traverse(preorderList, startIndex + 1, result);
        } else {
            result.add(currentNode.leftName);
        }

        // 处理右子树：rightName为null则递归遍历右子树，否则直接输出非null值
        if (currentNode.rightName == null) {
            nextIndex = traverse(preorderList, nextIndex, result);
        } else {
            result.add(currentNode.rightName);
        }

        return nextIndex;
    }

    // 测试示例
    public static void main(String[] args) {
        TreeTraversalConverter converter = new TreeTraversalConverter();

        // 示例1测试
        List<Node> preorder1 = new ArrayList<>();
        preorder1.add(new Node(null, null));
        preorder1.add(new Node("something1", "something2"));
        preorder1.add(new Node("otherthing1", "otherthing2"));
        System.out.println(String.join(", ", converter.convertPreorderToPostorder(preorder1)));
        // 输出：something1, something2, otherthing1, otherthing2

        // 示例2测试
        List<Node> preorder2 = new ArrayList<>();
        preorder2.add(new Node("something", null));
        preorder2.add(new Node("other", "secondOther"));
        preorder2.add(new Node("otherthing1", "otherthing2"));
        System.out.println(String.join(", ", converter.convertPreorderToPostorder(preorder2)));
        // 输出：something, other, secondOther, otherthing1, otherthing2
    }
}

代码说明 #

• traverse方法是核心：通过返回下一个节点索引，动态确定右子树的起始位置，完美解决你无法定位左子树结束索引的问题
• 严格遵循后序遍历逻辑：先处理左子树，再处理右子树，最后处理当前节点的输出内容
• 适配你描述的两种示例场景，运行结果与期望完全一致

内容的提问来源于stack exchange，提问作者Balázs Patai