计算二叉搜索树中的节点

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

在一个错误的answer.However上述功能的结果，下面的代码工作：

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