程序使用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