이진 트리의 내부 노드 (부모 노드)를 재귀 적으로 계산하기

Question

이진 검색 트리의 루트 노드를 매개 변수로 사용하는 재귀 적 메서드를 만들어야합니다. 이 재귀 적 메소드는 전체 바이너리 검색 트리에서 내부 노드의 총 수의 int 값을 반환합니다.

int countNrOfInnerNodes (Node node) { 
    if(node == null) { 
     return 0; 
    } 
    if (node.left != null && node.right != null){ 
     return 1; 
    } 
    return countNrOfInnerNodes(node.left)+countNrOfInnerNodes(node.right) 
    } 
} 

더 나은 방법이 있나요 :

이것은 내가 지금까지 가지고 무엇인가? 또한 iterativ 솔루션을 찾으려고했습니다.

Answer 1

여기서 재귀 적 방법은 고정이다 :

int countNrOfInnerNodes(Node node) { 
    if (node == null) 
     return 0; 

    Stack<Node> nodesToCheck = new Stack<Node>(); 

    nodesToCheck.push(node); 
    int count = 0; 

    while (!nodesToCheck.isEmpty()) { 
     Node checkedNode = nodesToCheck.pop(); 
     boolean isInnerNode = false; 

     if (node.left != null) { 
      isInnerNode = true; 
      nodesToCheck.push(node.left); 
     } 

     if (node.right != null) { 
      isInnerNode = true; 
      nodesToCheck.push(node.right); 
     } 

     if (isInnerNode) 
      count++; 
    } 

    return count; 
} 

:

가

int countNrOfInnerNodes (Node node) { 
    if(node == null) { 
     return 0; 
    } 

    if (node.left == null && node.right == null) { 
     // not an inner node ! 
     return 0; 
    } else { 
     // the number of inner nodes in the left sub-tree + the number of inner 
     // nodes in the right sub-tree, plus 1 for this inner node 
     return countNrOfInnerNodes(node.left) + countNrOfInnerNodes(node.right) + 1; 
    } 
} 

여기서 반복 메소드의