java - 计算二叉搜索树中的节点数

Question

我编写了以下递归函数来计算二叉搜索树中的总节点数。

class BST {
...........
int lc=0,rc=0;
int totalnodes(Node root){
    if(root==null)return 0;
    lc=totalnodes(root.left);
    rc=totalnodes(root.right);
    return rc+lc+1;
  }
}

上面的函数会导致错误的答案。但是，下面的代码可以工作:

    class BST {
    int totalnodes(Node root){
        if(root==null)return 0;     
        return totalnodes(root.left)+totalnodes(root.right)+1;
    }
   }

我在第一个功能中缺少什么。

Answer 1

您忽略了您的 lc 和 rc 不是本地的事实。因此，在对节点 root 计算 lc 后，它将被调用 totalnodes(root.left) 覆盖，而计算结果root 将稍后进行。

尝试将 lc、rc 声明移至方法:

int totalnodes(Node root){
    if(root==null)return 0;
    int lc=totalnodes(root.left);
    int rc=totalnodes(root.right);
    return rc+lc+1;
}