如何在递归遍历BST时定义共享变量以生成中序有序数组？

嘿，这个问题我之前在写BST中序遍历的时候也碰到过！其实要让递归的辅助方法能访问同一个ArrayList，有几种很实用的方案，我给你拆解一下：

方案1：把ArrayList作为参数传递给递归辅助方法 #

这是最常用也最灵活的方式——你在主方法里初始化好ArrayList，然后把它作为参数传给递归的辅助函数，每次递归调用都会操作同一个列表对象。

举个Java的例子：

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BSTTraversal {
    public List<Integer> getAllElements(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderTraverse(root, result);
        return result;
    }

    // 辅助递归方法，直接操作传入的result列表
    private void inorderTraverse(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        // 先遍历左子树（BST左子树元素更小）
        inorderTraverse(node.left, result);
        // 把当前节点值加入列表
        result.add(node.val);
        // 再遍历右子树
        inorderTraverse(node.right, result);
    }
}

这种方式的好处是无状态，不会依赖类的成员变量，多线程场景下也更安全，而且逻辑清晰，别人看代码一眼就能明白数据是怎么传递的。

方案2：将ArrayList定义为类的成员变量 #

如果你觉得传参有点麻烦，可以把ArrayList声明为当前类的成员变量，这样递归辅助方法就能直接访问它了。

示例代码：

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BSTTraversal {
    // 成员变量，供递归方法访问
    private List<Integer> result = new ArrayList<>();

    public List<Integer> getAllElements(TreeNode root) {
        result.clear(); // 注意每次调用前清空，避免保留上一次的遍历结果
        inorderTraverse(root);
        return result;
    }

    private void inorderTraverse(TreeNode node) {
        if (node == null) {
            return;
        }
        inorderTraverse(node.left);
        result.add(node.val);
        inorderTraverse(node.right);
    }
}

这个方案代码更简洁，但要注意每次调用getAllElements前必须清空成员变量，不然多次调用会把之前的结果也保留下来。另外如果是多线程环境，这种方式可能会有线程安全问题，需要额外加锁处理。

方案3：让递归方法返回子树的元素列表（函数式风格） #

还有一种更偏向函数式的写法，递归方法返回当前子树的所有元素列表，然后把左子树的列表、当前节点值、右子树的列表合并起来。

示例代码：

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BSTTraversal {
    public List<Integer> getAllElements(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> leftList = getAllElements(root.left);
        leftList.add(root.val);
        leftList.addAll(getAllElements(root.right));
        return leftList;
    }
}

这种写法不需要额外的辅助方法，代码更紧凑，但缺点是每次递归都会创建新的列表（或者合并列表），对于大型BST来说，性能会比前两种方案稍差一些，不过一般中小型树完全够用。

总结一下，如果追求灵活和线程安全，选方案1；如果想代码简洁，选方案2；如果喜欢函数式风格，选方案3～

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