이진 검색 트리의 노드 계산

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