이 튜토리얼에서는 바이너리 트리에서 가장 깊은 홀수 레벨 노드를 찾는 방법을 배울 것입니다.
이것은 이진 트리의 깊이를 찾는 것과 유사합니다. 여기에서 현재 레벨이 홀수인지 아닌지에 대한 조건이 하나 더 필요합니다.
문제를 해결하는 단계를 살펴보겠습니다.
-
더미 데이터로 바이너리 트리를 초기화합니다.
-
이진 트리에서 가장 깊은 홀수 레벨 노드를 찾는 재귀 함수를 작성하십시오.
-
현재 노드가 리프 노드이고 레벨이 홀수이면 현재 레벨을 반환합니다.
-
그렇지 않으면 재귀 함수 호출로 왼쪽 노드와 오른쪽 노드의 최대값을 반환합니다.
-
-
가장 깊은 홀수 레벨 노드를 인쇄합니다.
예시
코드를 봅시다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int data) {
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
int oddLeafDepthInTree(struct Node *root, int level) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL && level % 2 == 1) {
return level;
}
return max(oddLeafDepthInTree(root->left, level + 1), oddLeafDepthInTree(root->right, level + 1));
}
int main() {
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(5);
root->right->right = newNode(6);
root->right->left->right = newNode(7);
root->right->right->right = newNode(8);
int level = 1, depth = 0;
cout << oddLeafDepthInTree(root, level) << endl;
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
3
결론
튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.