在二叉搜索树中查找 int 数据大于 x 的节点数

Question

我正在尝试以递归方式查找 int 数据大于给定 int 的节点数。这是在二叉搜索树上完成的，因此在查找数量方面让事情变得更容易一些。但是，我的解决方案似乎对我运行的所有测试都是一次性的，我不明白为什么，请参见下文：

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

我知道我可以只搜索整棵树，但那样效率很低，而且没有真正利用二叉搜索树的结构。我可能在这里忽略了什么吗？我在这里的思考过程是向右走，因为那是最大的价值所在，但也许这是有缺陷的。

Answer 1

您想对值大于给定 int 的节点进行计数。但是当根值小于给定的 int 时，函数的基本情况 returns，这是相反的行为。

使用右子树的想法很好，但不是在发现更大的值时返回，而是必须做相反的事情。

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

编辑：您还需要在 null;

时处理节点

Answer 2

一些问题：

您的代码应该首先检查 r 是否为 null。
当你到达null时你只能return0。
当r.data > d时返回0肯定是错误的，因为应该计算该节点本身，以及右子树中的所有节点
您的代码从不查看左子树。当r.data > d时，左子树中也可能有节点需要计算。

这里更正：

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

或者使用三元运算符：

    private static int numGreaterThan(Node r, int d) {
        return r == null ? 0
             : numGreaterThan(r.right, d) +
                (d < r.data ? 1 + numGreaterThan(r.left, d) : 0);
    }

在二叉搜索树中查找 int 数据大于 x 的节点数

Finding the number of nodes with int data greater than x in a binary search tree

java

binary-search-tree