BST二叉搜索树中序遍历查找第n个节点时counter不递增问题排查

问题根因 #

counter被定义为BST类的实例成员变量，每个BST节点对象都会独立存储一份属于自己的counter值，不同节点的counter互不共享。递归调用左、右子节点的nth_node方法时，修改的是子节点自身的counter，和父节点的counter完全无关。因此每个节点执行counter++操作时，都是从初始值0加到1，最终所有节点输出的位置都为1。

修复方案 #

推荐使用传引用的局部counter方案，避免静态类成员的重入、多次调用残留值等问题，修改后的代码如下：

第一步：修改BST类定义 #

新增私有递归辅助函数，删除原有的实例counter成员：

#include <climits> // 引入头文件用INT_MIN作为未找到的标记

class BST {
public:
    int data;
    BST *left, *right;
    BST();
    BST(int);
    ~BST();
    void insert(int val);
    int nth_node(int n);
    int size();
private:
    // 递归辅助函数，counter用引用传递保证所有递归调用共享同一个计数器
    int nth_node_helper(int n, int& counter);
};

第二步：实现函数逻辑 #

int BST::nth_node_helper(int n, int& counter) {
    // 空节点直接返回未找到标记
    if (!this) return INT_MIN;

    // 先遍历左子树，左子树找到就直接返回，终止后续遍历
    int left_res = left->nth_node_helper(n, counter);
    if (left_res != INT_MIN) {
        return left_res;
    }

    // 访问当前节点
    counter++;
    std::cout << data << " (position: " << counter << "), " << std::endl;
    if (counter == n) { // 命中第n个节点，直接返回值
        return data;
    }

    // 最后遍历右子树
    return right->nth_node_helper(n, counter);
}

int BST::nth_node(int n) {
    int counter = 0; // 每次调用初始化全新的计数器
    return nth_node_helper(n, counter);
}

该方案的计数器仅在单次nth_node调用的生命周期内有效，不会和其他调用冲突，也不会污染类的成员变量，同时命中目标节点后会直接终止递归，不会做多余的遍历。

内容的提问来源于stack exchange，提问作者Branden-Pincince