각 노드를 방문하지 않고 완전한 이진 트리의 노드 수를 계산하는 방법은 무엇입니까? 나는 이것을 이해</p> <pre><code>public int countNodes(TreeNode root) { if (root == null) { return 0; } return 1 + countNodes(root.left) + countNodes(root.right); } </code></pre> <p>:

Question

은 내가 완전한 이진 트리에서 노드의 수를 계산에 사소한 해결책을 가지고 있습니다. 그러나 각 노드를 방문해야하므로 비효율적이라는 것을 알고 있습니다.

public int countNodes(TreeNode root) { 
    if(root==null) 
     return 0; 

    int left = getLeftHeight(root)+1;  
    int right = getRightHeight(root)+1; 

    if(left==right){ 
     return (2<<(left-1))-1; //having a hard time here 
    }else{ 
     return countNodes(root.left)+countNodes(root.right)+1; 
    } 
} 

public int getLeftHeight(TreeNode n){ 
    if(n==null) return 0; 

    int height=0; 
    while(n.left!=null){ 
     height++; 
     n = n.left; 
    } 
    return height; 
} 

public int getRightHeight(TreeNode n){ 
    if(n==null) return 0; 

    int height=0; 
    while(n.right!=null){ 
     height++; 
     n = n.right; 
    } 
    return height; 
} 

나는 이것을 이해하지만 난 상태 경우 (leftHeight == rightHeight을) 이해 완전히 확실하지 않다 : 나는 온라인으로 볼 다른 해결책이있다. 이게 어떻게 작동합니까? 또한, 누군가 비트 연산과 왜 이것이 작동하는지 이유를 설명해 주시겠습니까? 비트 연산자에 익숙하지 않아요. 어쩌면, 누군가가 비트가없는 코드로 그 상태를 대체 할 수 있다면, 그것은 완벽 할 것입니다.

Answer 1

우리가 알고있는 트리의 하위 트리에서 조건 (leftHight == rightHight)은 현재 하위 트리가 perfect (전체) 이진 트리임을 의미합니다. 완전한 이진 트리에서 모든 노드는 자식이없는 리프 노드를 제외하고 정확히 두 개의 자식을가집니다.

비트 문 (2<<(left-1))-1은 Math.pow(2, left) - 1과 동일합니다. 2의 일반적 권한에 은 다음과 같이 계산 될 수있다

2<<0 //equals 2 to the power of 1. 2 is shifted zero bits to the left 
2<<1 //equals 2 to the power of 2, 2 is shifted 1 bit to the left 
2<<2 // equals 2 to the power of 3, 2 is shifted 2 bits to the left 
2<<k // equals 2 to the power of k+1, 2 is shifted k bits to the left 

을 이제 높이 h의 완벽한 이진 트리의 노드 수는 (2**(k+1))-1 것을 볼 수 있습니다 위의이 링크를 보면. 이것은 (k + 1) -1의 거듭 제곱입니다.

위의 코드에서 left은 height+1입니다. 코드에서 +1을 확인하십시오. 거기에 (2<<(left-1))-1 실제로 그 완벽한 이진 트리에있는 노드를 계산합니다.