统计二叉搜索树中int数据大于给定值的节点数 递归实现偏差问题

你的实现存在三个本质错误，是导致结果偏差的直接原因：

• 逻辑判断完全写反：你设置的if(r.data > d) return 0，相当于直接放弃统计所有大于目标值的节点，反而在统计小于等于目标值的节点，和你的需求完全相反。
• 遗漏了左子树的符合条件节点：BST的特性是「左子树所有节点小于当前节点、右子树所有节点大于当前节点」，如果当前节点已经大于目标值，那它的左子树里也存在一部分大于目标值的节点，这部分你完全没有统计。
• 缺少空节点终止条件：一旦递归到叶子节点的子节点（null），访问r.data会直接触发空指针异常，你的代码能跑通只能说明测试用例刚好没有触发边界场景。

利用BST结构剪枝的逻辑如下：

1. 空节点没有值，直接返回0
2. 如果当前节点值大于目标值：当前节点本身要计数，加上右子树所有符合条件的节点，再加上左子树中符合条件的节点
3. 如果当前节点值小于等于目标值：当前节点和它的整个左子树都不可能大于目标值，只需要统计右子树的结果

对应代码实现：

private int numGreaterThan(Node r,int d) {
    if(r == null) return 0;
    if(r.data > d) {
        return 1 + numGreaterThan(r.right, d) + numGreaterThan(r.left, d);
    } else {
        return numGreaterThan(r.right, d);
    }
}

这个实现不需要遍历整棵树，会自动剪枝掉不可能符合条件的子树，时间复杂度最优是O(logn)，最坏才是O(n)，符合你要利用BST结构提升效率的需求。

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