C++에서 이진 트리의 대각선 순회에서 K번째 노드

이 튜토리얼에서는 이진 트리의 대각선 순회에서 k번째 노드를 찾는 프로그램을 작성할 것입니다.

문제를 해결하는 단계를 살펴보겠습니다.

• 몇 가지 샘플 데이터로 이진 트리를 초기화합니다.
• 숫자 k를 초기화합니다.
• 데이터 구조 대기열을 사용하여 대각선으로 이진 트리를 탐색합니다.
  • 각 노드에서 k 값을 감소시킵니다.
  • k가 0이 되면 노드를 반환합니다.
• 해당 노드가 없으면 -1을 반환합니다.

예시

코드를 봅시다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node *left, *right;
};
Node* getNewNode(int data) {
   Node* node = (Node*)malloc(sizeof(Node));
   node->data = data;
   node->left = node->right = NULL;
   return node;
}
int findDiagonalKthElement(Node* root, int k) {
   if (root == NULL || k == 0) {
      return -1;
   }
   int result = -1;
   queue<Node*> q;
   q.push(root);
   q.push(NULL);
   while (!q.empty()) {
      Node* temp = q.front();
      q.pop();
      if (temp == NULL) {
         if (q.empty()) {
            if (k == 0) {
               return result;
            }else {
               break;
            }
         }
         q.push(NULL);
      }else {
         while (temp) {
            if (k == 0) {
               return result;
            }
            k--;
            result = temp->data;
            if (temp->left) {
               q.push(temp->left);
            }
            temp = temp->right;
         }
      }
   }
   return -1;
}
int main() {
   Node* root = getNewNode(10);
   root->left = getNewNode(5);
   root->right = getNewNode(56);
   root->left->left = getNewNode(3);
   root->left->right = getNewNode(22);
   root->right->right = getNewNode(34);
   root->right->right->left = getNewNode(45);
   root->left->right->left = getNewNode(67);
   root->left->right->right = getNewNode(100);
   int k = 9;
   cout << findDiagonalKthElement(root, k) << endl;
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

67

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.