루트보다 높은 값의 이진 트리 노드 수를 확인하십시오.

-1

안녕하세요 다음과 같은 문제가 있습니다. 주어진 Tree를 감안할 때, 루트와 노드 위에있는 값보다 높은 값을 가진 노드의 수를 확인할 수 있기를 원합니다. 즉, 노드의 값이 11 인 경우 루트와 모든 노드보다 높거나 같으면 카운터를 늘려야합니다 (따라서 루트까지의 모든 값은 11보다 작거나 같아야 함). 최선을 달성하는 방법? 루트보다 높은 값의 이진 트리 노드 수를 확인하십시오.

는

출처

2012-01-28 aretai

[무엇을 시도해 봤습니까?] (http://mattgemmell.com/2008/12/08/what-have-you-tried/) –

이 숙제입니까? 그냥 똑바로 오른쪽으로 +1! – Gevorg

이 구체적으로이 질문에 대답하도록 구성된 구조입니까? 즉, 왼쪽 노드가 상위 노드보다 작거나 같은 이진 트리입니까? 오른쪽 노드가 상위 노드보다 큽니 까? 그렇다면 매우 간단해야합니다. 그렇지 않다면 왜 처음에 나무를 사용하는지 모르겠습니다. 문맥 정보가 조금 더 많으면 문제에 대한 유용한 답을 얻을 수 있습니다. –

가 breadth first 트리 탐색을 수행 감사합니다. 각 레벨의 끝에서 카운터 값을 비교하는 데 사용되는 해시 테이블에 노드 값 (해당 레벨에만 해당)을 추가하십시오.

    2 
      /  \ 
      1   3 
     / \  / \ 
     11  12 4  5

송출 : LVL에

해시 테이블은 = {}

방문하는 모든 노드. 1
val = 2. 루트 및 모두보다 큼 (hashTable)? 예. Incr. 계수기. hashTable에 모두를 추가하십시오. 다음 lvl로 이동하십시오.

해시 테이블 = {2}

발 = 루트 1보다 큰 모든 (해시 테이블)? 아니요. 이웃 방문
val = 3. 루트 및 모두보다 큼 (hashTable)? 예. Incr. 계수기. hashTable에 모두를 추가하십시오. 다음 lvl로 이동하십시오.

해시 테이블 = {2, 1, 3}

. . .

count = 6 노드는 그 위의 모든 노드보다 크거나 같습니다.

출처

2012-01-29 01:33:35 blackcompe

감사합니다. – aretai

루트보다 높은 값의 이진 트리 노드 수를 확인하십시오.

답변

관련 문제