Java实现AVL树后序遍历如何将结果存入字符串而非控制台

你只需要把递归逻辑里「打印到控制台」的操作，替换为「向可变字符串容器追加内容」即可，Java中优先使用StringBuilder做字符串拼接，避免不可变String拼接产生的大量临时对象开销。

注意递归过程中要传递同一个StringBuilder实例，保证所有节点的内容都能追加到同一字符串中，不要在每层递归里新建字符串容器。

后序遍历改造示例 #

/**
 * 对外暴露的入口方法，传入AVL树根节点，返回后序遍历结果字符串
 * @param root 树的根节点
 * @return 空格分隔的后序遍历结果
 */
public String getPostorderResult(Node root) {
    StringBuilder resultContainer = new StringBuilder();
    doPostorderTraverse(root, resultContainer);
    // 去除末尾多余的空格，不需要可以去掉trim()
    return resultContainer.toString().trim();
}

/**
 * 内部递归遍历方法，复用同一个StringBuilder拼接结果
 */
private void doPostorderTraverse(Node node, StringBuilder sb) {
    if (node == null) {
        return;
    }
    // 遍历左子树
    doPostorderTraverse(node.left, sb);
    // 遍历右子树
    doPostorderTraverse(node.right, sb);
    // 处理根节点：把原来的System.out.print替换为追加到StringBuilder
    sb.append(node.element).append(" ");
}

前序、中序遍历的改造逻辑 #

三种遍历的改造逻辑完全一致，只需要调整追加当前节点内容的位置即可：

• 前序遍历（根-左-右）：先执行sb.append(node.element).append(" ")，再递归遍历左、右子树
• 中序遍历（左-根-右）：先递归左子树，再执行追加操作，最后递归右子树
• 后序遍历（左-右-根）：即上述示例的写法，先递归左右子树，最后追加当前节点

不推荐的写法 #

不要直接让递归方法返回String做拼接，类似下面的代码：

// 不推荐：节点数量较多时会产生大量临时String对象，性能很差
public String badPostorderImpl(Node node) {
    if (node == null) return "";
    String left = badPostorderImpl(node.left);
    String right = badPostorderImpl(node.right);
    return left + right + node.element + " ";
}

这种写法因为Java String是不可变类型，每次+拼接都会生成新的字符串对象，树规模大时内存和时间开销都会明显升高。

内容的提问来源于stack exchange，提问作者RoronoaNewJavaBoy