如何通过二叉树中序遍历存储节点元素并生成结果字符串

你的代码主要存在几个问题：

• 语法错误：第二个返回字符串的版本里node.getElement())多了一个右括号，return s末尾没加分号；第一个打印版本的方法是void类型却返回了""，属于编译错误；
• 递归传递s参数导致重复拼接：每次递归调用都把当前的s传进去，子递归会基于已有内容再拼接，最终导致节点内容被多次重复添加；
• 使用String拼接效率低：String是不可变对象，每次+=都会生成新的字符串实例，树节点较多时性能很差。

修正方案1：修复递归逻辑（基于String） #

去掉递归时传递的s参数，让每个递归调用只负责返回当前子树的中序遍历字符串，再在当前层拼接左右子树和当前节点的内容：

private String searchAndStore(Node node) {
    if (node == null) {
        return "";
    }
    // 注意：二叉搜索树标准升序中序遍历是「左-根-右」，你原代码写的是「右-根-左」会得到降序结果，可根据需求调整
    String leftStr = searchAndStore(node.getL());
    String currentStr = node.getElement().toString();
    String rightStr = searchAndStore(node.getR());
    return leftStr + currentStr + rightStr;
}

更优方案2：使用StringBuilder提升效率 #

考虑到String拼接的性能问题，推荐用StringBuilder构建字符串，同时可以顺便把元素存入数组：

// 用于存储节点元素的集合（可按需转为数组）
private List<Object> elementList = new ArrayList<>();

private String searchAndStore(Node node) {
    StringBuilder sb = new StringBuilder();
    traverse(node, sb);
    // 若需要将集合转为数组
    Object[] elementArray = elementList.toArray();
    return sb.toString();
}

private void traverse(Node node, StringBuilder sb) {
    if (node == null) {
        return;
    }
    // 左-根-右 升序遍历，要降序则调整为「右-根-左」
    traverse(node.getL(), sb);
    Object element = node.getElement();
    sb.append(element);
    elementList.add(element);
    traverse(node.getR(), sb);
}

原代码出现「节点多次访问」假象的原因 #

你在递归时把当前的s传入子调用，比如第一次调用s为空，拼接右子树结果时，右子树的递归会基于这个已有s再拼接内容，导致父层的内容被重复带入子递归的拼接过程，最终字符串里会出现大量重复的节点元素，看起来像是节点被多次访问，实际是重复拼接了内容。

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