原文：
给定具有不同值的二叉树，任务是打印第一个最小的根到叶路径。 我们基本上需要打印出节点数最少的最左边的根到叶的路径。
input:
1
/ \
2 3
/ / \
4 5 7
/ \ \
10 11 8
output: 1 3 5
input:
1
/ \
2 3
/ / \
40 5 7
\
8
output: 1 2 40
方法：这个想法是使用队列执行，即映射parent来存储将出现在最短路径中的节点。 使用层次顺序遍历，我们找到最左边的叶子。 找到最左边的叶子后，便使用映射打印路径。
下面是上述方法的实现：
c
// c program to print first shortest
// root to leaf path
#include
using namespace std;
// binary tree node
struct node {
struct node* left;
struct node* right;
int data;
};
// function to create a new
// binary node
struct node* newnode(int data)
{
struct node* temp = new node;
temp->data = data;
temp->left = null;
temp->right = null;
return temp;
}
// recursive function used by leftmostshortest
// to print the first shortest root to leaf path
void printpath(int data, unordered_map parent)
{
// if the root's data is same as
// its parent data then return
if (parent[data] == data)
return;
// recur for the function printpath
printpath(parent[data], parent);
// print the parent node's data
cout << parent[data] << " ";
}
// function to perform level order traversal
// until we find the first leaf node
void leftmostshortest(struct node* root)
{
// queue to store the nodes
queue q;
// push the root node
q.push(root);
// initialize the value of first
// leaf node to occur as -1
int leafdata = -1;
// to store the current node
struct node* temp = null;
// map to store the parent node's data
unordered_map parent;
// parent of root data is set as it's
// own value
parent[root->data] = root->data;
// we store first node of the smallest level
while (!q.empty()) {
temp = q.front();
q.pop();
// if the first leaf node has been found
// set the flag variable as 1
if (!temp->left && !temp->right) {
leafdata = temp->data;
break;
}
else {
// if current node has left
// child, push in the queue
if (temp->left) {
q.push(temp->left);
// set temp's left node's parent as temp
parent[temp->left->data] = temp->data;
}
// if current node has right
// child, push in the queue
if (temp->right) {
q.push(temp->right);
// set temp's right node's parent
// as temp
parent[temp->right->data] = temp->data;
}
}
}
// recursive function to print the first
// shortest root to leaf path
printpath(leafdata, parent);
// print the leaf node of the first
// shortest path
cout << leafdata << " ";
}
// driver code
int main()
{
struct node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->right->left = newnode(5);
root->right->right = newnode(7);
root->left->left->left = newnode(10);
root->left->left->right = newnode(11);
root->right->right->left = newnode(8);
leftmostshortest(root);
return 0;
}
java
// java program to print first shortest
// root to leaf path
import java.util.*;
class gfg{
// binary tree node
static class node
{
node left;
node right;
int data;
};
// function to create a new
// binary node
static node newnode(int data)
{
node temp = new node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
// recursive function used by leftmostshortest
// to print the first shortest root to leaf path
static void printpath(int data,
hashmap parent)
{
// if the root's data is same as
// its parent data then return
if (parent.get(data) == data)
return;
// recur for the function printpath
printpath(parent.get(data), parent);
// print the parent node's data
system.out.print(parent.get(data) " ");
}
// function to perform level order traversal
// until we find the first leaf node
static void leftmostshortest(node root)
{
// queue to store the nodes
queue q = new linkedlist<>();
// add the root node
q.add(root);
// initialize the value of first
// leaf node to occur as -1
int leafdata = -1;
// to store the current node
node temp = null;
// map to store the parent node's data
hashmap parent = new hashmap<>();
// parent of root data is set as it's
// own value
parent.put(root.data, root.data);
// we store first node of the smallest level
while (!q.isempty())
{
temp = q.poll();
// if the first leaf node has been found
// set the flag variable as 1
if (temp.left == null &&
temp.right == null)
{
leafdata = temp.data;
break;
}
else
{
// if current node has left
// child, add in the queue
if (temp.left != null)
{
q.add(temp.left);
// set temp's left node's parent
// as temp
parent.put(temp.left.data,
temp.data);
}
// if current node has right
// child, add in the queue
if (temp.right != null)
{
q.add(temp.right);
// set temp's right node's parent
// as temp
parent.put(temp.right.data,
temp.data);
}
}
}
// recursive function to print the
// first shortest root to leaf path
printpath(leafdata, parent);
// print the leaf node of the first
// shortest path
system.out.println(leafdata " ");
}
// driver code
public static void main(string[] args)
{
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.right.left = newnode(5);
root.right.right = newnode(7);
root.left.left.left = newnode(10);
root.left.left.right = newnode(11);
root.right.right.left = newnode(8);
leftmostshortest(root);
}
}
// this code is contributed by sanjeev2552
python3
# python3 program to print first
# shortest root to leaf path
# binary tree node
class node:
def __init__(self, data):
self.data = data
self.left = none
self.right = none
# recursive function used by leftmostshortest
# to print the first shortest root to leaf path
def printpath(data, parent):
# if the root's data is same as
# its parent data then return
if parent[data] == data:
return
# recur for the function printpath
printpath(parent[data], parent)
# print the parent node's data
print(parent[data], end = " ")
# function to perform level order traversal
# until we find the first leaf node
def leftmostshortest(root):
# queue to store the nodes
q = []
# push the root node
q.append(root)
# initialize the value of first
# leaf node to occur as -1
leafdata = -1
# to store the current node
temp = none
# map to store the parent node's data
parent = {}
# parent of root data is set
# as it's own value
parent[root.data] = root.data
# we store first node of the
# smallest level
while len(q) != 0:
temp = q.pop(0)
# if the first leaf node has been
# found set the flag variable as 1
if not temp.left and not temp.right:
leafdata = temp.data
break
else:
# if current node has left
# child, push in the queue
if temp.left:
q.append(temp.left)
# set temp's left node's parent as temp
parent[temp.left.data] = temp.data
# if current node has right
# child, push in the queue
if temp.right:
q.append(temp.right)
# set temp's right node's parent
# as temp
parent[temp.right.data] = temp.data
# recursive function to print the first
# shortest root to leaf path
printpath(leafdata, parent)
# print the leaf node of the
# first shortest path
print(leafdata, end = " ")
# driver code
if __name__ == "__main__":
root = node(1)
root.left = node(2)
root.right = node(3)
root.left.left = node(4)
root.right.left = node(5)
root.right.right = node(7)
root.left.left.left = node(10)
root.left.left.right = node(11)
root.right.right.left = node(8)
leftmostshortest(root)
# this code is contributed by rituraj jain
c
// c# program to print first shortest
// root to leaf path
using system;
using system.collections;
using system.collections.generic;
class gfg{
// binary tree node
public class node
{
public node left;
public node right;
public int data;
};
// function to create a new
// binary node
public static node newnode(int data)
{
node temp = new node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
// recursive function used by leftmostshortest
// to print the first shortest root to leaf path
static void printpath(int data,
dictionary parent)
{
// if the root's data is same as
// its parent data then return
if (parent[data] == data)
return;
// recur for the function printpath
printpath(parent[data], parent);
// print the parent node's data
console.write(parent[data] " ");
}
// function to perform level order traversal
// until we find the first leaf node
static void leftmostshortest(node root)
{
// queue to store the nodes
queue q = new queue();
// add the root node
q.enqueue(root);
// initialize the value of first
// leaf node to occur as -1
int leafdata = -1;
// to store the current node
node temp = null;
// map to store the parent node's data
dictionary parent = new dictionary();
// parent of root data is set as it's
// own value
parent[root.data] = root.data;
// we store first node of the
// smallest level
while (q.count != 0)
{
temp = (node)q.dequeue();
// if the first leaf node has been
// found set the flag variable as 1
if (temp.left == null &&
temp.right == null)
{
leafdata = temp.data;
break;
}
else
{
// if current node has left
// child, add in the queue
if (temp.left != null)
{
q.enqueue(temp.left);
// set temp's left node's parent
// as temp
parent[temp.left.data] = temp.data;
}
// if current node has right
// child, add in the queue
if (temp.right != null)
{
q.enqueue(temp.right);
// set temp's right node's parent
// as temp
parent[temp.right.data] = temp.data;
}
}
}
// recursive function to print the
// first shortest root to leaf path
printpath(leafdata, parent);
// print the leaf node of the first
// shortest path
console.write(leafdata " ");
}
// driver code
public static void main(string[] args)
{
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.right.left = newnode(5);
root.right.right = newnode(7);
root.left.left.left = newnode(10);
root.left.left.right = newnode(11);
root.right.right.left = newnode(8);
leftmostshortest(root);
}
}
// this code is contributed by rutvik_56
输出：
1 3 5
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
