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;
}