이진 트리의 높이를 찾는 반복 방법

이진 트리는 데이터 구조입니다. 이진 트리의 각 노드에는 0, 1 또는 2개의 노드가 포함됩니다. 따라서 이진 트리에는 여러 수준이 포함될 수 있습니다.

여기서 루프를 사용하여 이진 트리의 높이를 찾는 반복 코드를 작성해야 합니다. 이진 트리의 총 레벨 수는 이진 트리의 높이를 나타냅니다. 또는 루트 노드에서 이진 트리의 최대 깊이가 이진 트리의 높이라고 말할 수 있습니다.

문제 설명 - 이진 트리가 제공됩니다. 주어진 이진 트리의 높이를 찾으려면 반복 방법을 사용해야 합니다.

방법 1

위에서 말했듯이 이진 트리의 높이는 이진 트리의 총 레벨 수와 같습니다. 우리는 큐 데이터 구조를 사용하여 각 레벨의 각 노드를 반복하고 트리의 최대 깊이를 찾습니다.

알고리즘

1단계 - "treeNode" 클래스를 정의하고 "val" 정수 변수를 추가합니다. 또한 클래스에서 "왼쪽" 및 "오른쪽" 포인터를 정의합니다.

2단계 - createNode() 함수를 정의하여 트리에 대한 새 노드를 만듭니다. 새 treeNode를 생성하고 매개변수 값으로 "val"을 초기화하며 null 값으로 왼쪽 및 오른쪽 포인터를 초기화합니다. 마지막으로 새로 생성된 노드를 반환합니다.

3단계 - findHeight() 함수는 이진 트리의 높이를 찾는 데 사용됩니다.

4단계 - 현재 레벨의 모든 노드, "treeHeight", "n_cnt" 변수 및 "temp" 노드를 저장하는 "levelqueue" 대기열을 정의합니다.

5단계− 헤드 노드가 Null이면 0을 반환합니다.

6단계 - 헤드 노드를 "levelQueue"로 푸시합니다.

7단계 - "while" 루프를 사용하여 "levelQueue"가 비워질 때까지 반복합니다.

8단계 - "treeHeight"를 1만큼 늘리고 현재 수준의 총 노드 수를 나타내는 대기열 크기로 "n_cnt"를 초기화합니다.

9단계 - 대기열의 모든 요소를 ​​반복합니다.

9.1단계 - 대기열의 첫 번째 요소를 팝합니다.

9.2단계 − 현재 노드에 왼쪽 자식 노드가 있으면 이를 대기열에 삽입합니다.

9.3단계 − 현재 노드에 올바른 자식 노드가 있으면 이를 대기열에 삽입합니다.

9.4단계 - 대기열에서 첫 번째 노드를 제거합니다.

10단계 - "treeHeight" 변수의 값을 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도 - 각 노드를 통과하는 데 O(N)입니다.

공간 복잡성 - 대기열에 노드를 저장하는 O(N)입니다.

문제를 해결할 때 반복 방법은 항상 재귀 방법보다 빠릅니다. 여기서는 루프와 큐를 사용하여 이진 트리의 최대 깊이 또는 높이를 반복적으로 찾습니다. 그러나 프로그래머는 이진 트리의 높이를 찾기 위해 재귀 메서드를 코딩하려고 할 수도 있습니다.

위 내용은 이진 트리의 높이를 찾는 반복 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!