计数二叉搜索树中小于键的节点数

Question

已经为此工作了几个小时，但我似乎仍然无法提出一个可行的解决方案。11.13 二叉树引导信息流 X279：二叉搜索树小计数练习

Answer 1

我的第一个答案没有用。这个新的可以。

第一个问题是你实际上没有计算任何东西，你只是递归地遍历每个节点并检查它的值。

其次，检查也没有按预期工作。您必须检查是否应计算当前节点。您还应该进一步向下计算树，因为这些节点可能小于键。

我的工作实施：

public int BSTsmallcount(BinNode root, int key)

{

    int count = 0;

    if (root == null) {

        return 0;

    }

    else if (root.value() < key) {

        count++;

        count += BSTsmallcount(root.left(), key);

        count += BSTsmallcount(root.right(), key);

    }

    else {

        count += BSTsmallcount(root.left(), key);

    }

    return count;

}