用 C++ 编程打印二叉树中第一个最短的根到叶子路径。

在给定的二叉树中，程序必须找出一条最短的根到叶路径。

由于我们是从左到右遍历这棵树，因此，如果从根到叶有多条最短路径，那么程序将打印从树的左侧遍历到的第一条最短路径。

我们可以使用一个队列，用层次遍历遍历每一层，而层数最少的路径将被打印出来，因为它是从根到叶的最短路径

在上面的树中，从根到叶的多条路径为

10 -> 3 (this one is the shortest path amongst all)
10 -> 211 -> 100
10 -> 211 -> 146

示例

Input  : 10 3 211 100 146
Output : 10 3

算法

Step 1 -> create a structure of a node as
   struct node
      struct node *left, *right
      int data
   End
Step 2 -> function to create a node
   node* newnode(int data)
   node *temp = new node
   temp->data = data
   temp->left = temp->right= NULL
   return temp
Step 3 -> create function for calculating path
   void path(int data, unordered_map <int,int> prnt)
      IF prnt[data] = data
         Return
      End
      path(prnt[data], prnt)
      print prnt[data]
step 4 -> function for finding out the left path
   void left(Node* root)
   create STL queue<Node*> que
   que.push(root)
   int leaf = -1
   Node* temp = NULL
   Create STL unordered_map<int, int> prnt
   prnt[root->data] = root->data
   Loop While !que.empty()
      temp = que.front()
      que.pop()
      IF !temp->left && !temp->right
         leaf = temp->data
         break
      End
      Else
         IF temp->left
            que.push(temp->left)
            prnt[temp->left->data] = temp->data
         End
         IF temp->right
            que.push(temp->right)
            prnt[temp->right->data] = temp->data
         End
      End
   End
   path(leaf, prnt)
   print leaf
Step 5 -> In main()
   Create tree using Node* root = newnode(90)
   root->left = newnode(21)
   call left(root)
stop

示例

 实时演示

#include <bits/stdc++.h>
using namespace std;
// structure of a node
struct Node {
   struct Node *left,*right;
   int data;
};
//function to create a new node
Node* newnode(int data){
   Node* temp = new Node;
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
//function to set a path
void path(int data, unordered_map <int,int> prnt) {
   if (prnt[data] == data)
      return;
   path(prnt[data], prnt);
   cout << prnt[data] << " ";
}
//function for a leaf path
void left(Node* root) {
   queue<Node*> que;
   que.push(root);
   int leaf = -1;
   Node* temp = NULL;
   unordered_map<int, int> prnt;
   prnt[root->data] = root->data;
   while (!que.empty()){
      temp = que.front();
      que.pop();
      if (!temp->left && !temp->right{
         leaf = temp->data;
         break;
      } else {
         if (temp->left){
            que.push(temp->left);
            prnt[temp->left->data] = temp->data;
         }
         if (temp->right){
            que.push(temp->right);
            prnt[temp->right->data] = temp->data;
         }
      }
   }
   path(leaf, prnt);
   cout << leaf << " ";
}
int main(){
   Node* root = newnode(90);
   root->left = newnode(21);
   root->right = newnode(32);
   root->left->left = newnode(45);
   root->right->left = newnode(52);
   root->right->right = newnode(27);
   root->left->left->left = newnode(109);
   root->left->left->right = newnode(101);
   root->right->right->left = newnode(78);
   left(root);
   return 0;
}

输出

如果我们运行以上程序，则会生成以下输出

90 32 52

Sunidhi Bansal

更新日期：04-Sep-2019

126 人浏览过

开启你的职业生涯

通过完成课程获得认证

开始学习