C++を使用してバイナリツリーの最初の最短ルートからリーフパスを出力するプログラム

このチュートリアルでは、バイナリツリーで最初の最短のルートからリーフへのパスを出力するプログラムについて説明します。

ここでは、異なる値を持つ二分木が与えられ、与えられた二分木でルートノードからリーフノードへの最短経路を見つける必要があります。

これを解決するために、キューを使用してバイナリツリーでレベル順トラバーサルを実行し、ノードを最短パスに格納できます。このため、最終レベルの左端のノードに到達すると、キューから値を取得し、最短パスを出力します。

例

#include <bits/stdc++.h>
using namespace std;
struct Node{
   struct Node* left;
   struct Node* right;
   int data;
};
struct Node* create_node(int data){
   struct Node* temp = new Node;
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
void print_spath(int Data, unordered_map<int, int> parent){
   if (parent[Data] == Data)
      return;
   print_spath(parent[Data], parent);
   cout << parent[Data] << " ";
}
void leftmost_path(struct Node* root){
   queue<struct Node*> q;
   q.push(root);
   int LeafData = -1;
   struct Node* temp = NULL;
   unordered_map<int, int> parent;
   parent[root->data] = root->data;
   while (!q.empty()){
      temp = q.front();
      q.pop();
      if (!temp->left && !temp->right){
         LeafData = temp->data;
      break;
      }
      else{
         if (temp->left){
            q.push(temp->left);
            parent[temp->left->data] = temp->data;
         }
         if (temp->right) {
            q.push(temp->right);
            parent[temp->right->data] = temp->data;
         }
      }
   }
   print_spath(LeafData, parent);
   cout << LeafData << " ";
}
int main(){
   struct Node* root = create_node(21);
   root->left = create_node(24);
   root->right = create_node(35);
   root->left->left = create_node(44);
   root->right->left = create_node(53);
   root->right->right = create_node(71);
   root->left->left->left = create_node(110);
   root->left->left->right = create_node(91);
   root->right->right->left = create_node(85);
   leftmost_path(root);
   return 0;
}

出力

21 35 53