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

結論

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。