計算二叉搜索樹中的節點

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