原文:
给定一个 二叉树 ，每一级 l 的任务是打印该树的 l th 节点。如果任何级别都不存在 l th 节点，则打印 -1 。
注意:考虑根节点在二叉树的 1 级。
示例:
输入:下面是给定的树: 输出: 级别 1: 1 级别 2: 3 级别 3: 6 级别 4: 11 说明: 对于第一个级别，第一个节点为 1。 对于第二层，第二个节点为 3。 对于第三级，第三节点为 6。 对于第四个级别，第四个节点是 11。
输入:下面是给定的树: 输出: 级别 1: 1 级别 2: 3 级别 3: 6 级别 4: -1 说明: 对于第一个级别，第一个节点为 1。 对于第二层，第二个节点为 3。 对于第三级，第三节点为 6。 对于第四级，第四节点不可用。因此，print -1。
方法:解决这个问题的思路是使用。按照以下步骤解决问题:
- 并将每个节点的级别和节点的值存储在多地图中。
- 节点的级别被认为是多重映射的关键。记录二叉树的最大
- 现在，在范围【1，l】内迭代多重映射，并执行以下操作:
- 对于每一级 l ，遍历至该级的 l 第t5】节点，检查是否存在。如果发现存在，打印该节点的值。
- 否则，打印-1”，进入下一级。
下面是上述方法的实现:
c
// c program for the above approach
#include
using namespace std;
// stores the level of the node and
// its value at the max level of bt
multimap m;
// stores the maximum level
int maxlevel = 0;
// structure of binary tree
struct node {
int data;
struct node* left;
struct node* right;
};
// function to insert the node in
// the binary tree
struct node* newnode(int d)
{
struct node* temp
= (struct node*)malloc(
sizeof(struct node));
temp->data = d;
temp->left = null;
temp->right = null;
return temp;
}
// function to find node of nth level
void findnode(struct node* root, int level)
{
// if root exists
if (root) {
// traverse left subtree
findnode(root->left, level 1);
// insert the node's level and
// its value into the multimap
m.insert({ level, root->data });
// update the maximum level
maxlevel = max(maxlevel, level);
// traverse the right subtree
findnode(root->right, level 1);
}
}
// function to print the l-th node at
// l-th level of the binary tree
void printnode(struct node* root, int level)
{
// function call
findnode(root, level);
// iterator for traversing map
multimap::iterator it;
// iterate all the levels
for (int i = 0; i <= maxlevel; i ) {
// print the current level
cout << "level " << i 1 << ": ";
it = m.find(i);
int flag = 0;
// iterate upto i-th node of the
// i-th level
for (int j = 0; j < i; j ) {
it ;
// if end of the level
// is reached
if (it == m.end()) {
flag = 1;
break;
}
}
// if i-th node does not exist
// in the i-th level
if (flag == 1 || it->first != i) {
cout << "-1" << endl;
}
// otherwise
else {
// print the i-th node
cout << it->second << endl;
}
}
}
// driver code
int main()
{
// construct the binary tree
struct node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->left->right->left = newnode(11);
root->left->right->right = newnode(12);
root->left->left->left = newnode(9);
root->left->left->right = newnode(10);
root->right->left = newnode(6);
root->right->right = newnode(7);
root->right->right->left = newnode(13);
root->right->right->right = newnode(14);
// function call
printnode(root, 0);
}
output:
level 1: 1
level 2: 3
level 3: 6
level 4: 12
时间复杂度: o(n)，其中 n 是二叉树中的节点数。 辅助空间: o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
