原文:
给定一个二叉树，任务是打印二叉树的每个
示例:
输入:下面是给定的树:
输出: 1 2 3 5 10 11 6 7 9 说明: 每一级的中间节点为: 级 0–1 级 1–2 和 3 级 2–5 和 10 级 3–11 和 6 级 4–7 和 9
输入:下面是给定的树:
输出: 1 2 3 5 8 9 11 12 13 15 14 说明: 每一级的中间节点为: 级 0–1 级 1–2 和 3 级 2–5 级 3–8 和 9 级 4–11 级 5–12 和 13
方法:想法是在给定的树上执行 的图中。现在遍历地图并相应地打印中间节点。以下是步骤:
- 初始化一个向量图 m 来存储一个向量中每个级别对应的所有节点。
- 对给定的树执行 ，从0 级开始，调用左右子树，在该级中增加 1 。
- 将上述 dfs 遍历中每一级对应的所有节点存储为 m【级】。push_back(root- >数据)。
- 现在，遍历地图 m 并对每个级别执行以下操作:
- 在地图 m 中找到与每个关卡相关的矢量(比如说 a )的大小(比如说 s )。
- 如果 s 为奇数，则只需将a[(s–1)/2]的值打印为中间的 (s/2) 第 节点。
- 否则打印a【(s–1)/2】和a【(s–1)/2 1】的值作为中间 (s/2) 第 和 ((s/2) 1) 第 第节点。
下面是上述方法的实现:
c
// c program for the above approach
#include
using namespace std;
// structure node of binary tree
struct node {
int data;
struct node* left;
struct node* right;
};
// function to create a new node
struct node* newnode(int d)
{
struct node* temp
= (struct node*)malloc(
sizeof(struct node));
temp->data = d;
temp->left = null;
temp->right = null;
// return the created node
return temp;
}
// function that performs the dfs
// traversal on tree to store all the
// nodes at each level in map m
void dfs(node* root, int l,
map >& m)
{
// base case
if (root == null)
return;
// push the current level node
m[l].push_back(root->data);
// left recursion
dfs(root->left, l 1, m);
// right recursion
dfs(root->right, l 1, m);
}
// function that print all the middle
// nodes for each level in binary tree
void printmidnodes(node* root)
{
// stores all node in each level
map > m;
// perform dfs traversal
dfs(root, 0, m);
// traverse the map m
for (auto& it : m) {
// get the size of vector
int size = it.second.size();
// for odd number of elements
if (size & 1) {
// print (m/2)th element
cout << it.second[(size - 1) / 2]
<< endl;
}
// otherwise
else {
// print (m/2)th and
// (m/2 1)th element
cout << it.second[(size - 1) / 2]
<< ' '
<< it.second[(size - 1) / 2 1]
<< endl;
}
}
}
// driver code
int main()
{
/*
binary tree shown below is:
1
/ \
2 3
/ \ / \
4 5 10 8
/ \
11 6
/ \
7 9
*/
// given 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(6);
root->left->right->right->left = newnode(7);
root->left->right->right->right = newnode(9);
root->right->left = newnode(10);
root->right->right = newnode(8);
// function call
printmidnodes(root);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program for
// the above approach
import java.util.*;
class gfg{
static map > m;
// structure node of
// binary tree
static class node
{
int data;
node left;
node right;
public node() {}
public node(int data,
node left,
node right)
{
super();
this.data = data;
this.left = left;
this.right = right;
}
};
// function to create a new node
static node newnode(int d)
{
node temp = new node();
temp.data = d;
temp.left = null;
temp.right = null;
// return the created node
return temp;
}
// function that performs the dfs
// traversal on tree to store all the
// nodes at each level in map m
static void dfs(node root, int l)
{
// base case
if (root == null)
return;
// push the current level node
if(!m.containskey(l))
{
vector temp = new vector();
temp.add(root.data);
m.put(l, temp);
}
else
m.get(l).add(root.data);
// left recursion
dfs(root.left, l 1);
// right recursion
dfs(root.right, l 1);
}
// function that print all the middle
// nodes for each level in binary tree
static void printmidnodes(node root)
{
// stores all node in each level
m = new hashmap >();
// perform dfs traversal
dfs(root, 0);
// traverse the map m
for (map.entry> it : m.entryset())
{
// get the size of vector
int size = it.getvalue().size();
// for odd number of elements
if (size % 2 == 1)
{
// print (m/2)th element
system.out.print(it.getvalue().get((size - 1) / 2) "\n");
}
// otherwise
else
{
// print (m/2)th and
// (m/2 1)th element
system.out.print(it.getvalue().get((size - 1) / 2) " "
it.getvalue().get(((size - 1) / 2) 1) "\n");
}
}
}
// driver code
public static void main(string[] args)
{
/*
binary tree shown below is:
1
/ \
2 3
/ \ / \
4 5 10 8
/ \
11 6
/ \
7 9
*/
// given tree
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(6);
root.left.right.right.left = newnode(7);
root.left.right.right.right = newnode(9);
root.right.left = newnode(10);
root.right.right = newnode(8);
// function call
printmidnodes(root);
}
}
//this code is contributed by 29ajaykumar
python 3
# python3 program for the above approach
# structure node of binary tree
class node:
def __init__(self, data):
self.data = data
self.left = none
self.right = none
# function to create a new node
def newnode(d):
temp = node(d)
# return the created node
return temp
# function that performs the dfs
# traversal on tree to store all the
# nodes at each level in map m
def dfs(root, l, m):
# base case
if (root == none):
return
# push the current level node
if l not in m:
m[l] = []
m[l].append(root.data)
# left recursion
dfs(root.left, l 1, m)
# right recursion
dfs(root.right, l 1, m)
# function that print all the middle
# nodes for each level in binary tree
def printmidnodes(root):
# stores all node in each level
m = dict()
# perform dfs traversal
dfs(root, 0, m)
# traverse the map m
for it in m.values():
# get the size of vector
size = len(it)
# for odd number of elements
if (size & 1):
# print (m/2)th element
print(it[(size - 1) // 2])
# otherwise
else:
# print (m/2)th and
# (m/2 1)th element
print(str(it[(size - 1) // 2]) ' '
str(it[(size - 1) // 2 1]))
# driver code
if __name__=="__main__":
'''
binary tree shown below is:
1
/ \
2 3
/ \ / \
4 5 10 8
/ \
11 6
/ \
7 9
'''
# given tree
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(6)
root.left.right.right.left = newnode(7)
root.left.right.right.right = newnode(9)
root.right.left = newnode(10)
root.right.right = newnode(8)
# function call
printmidnodes(root)
# this code is contributed by rutvik_56
c
// c# program for
// the above approach
using system;
using system.collections;
using system.collections.generic;
class gfg{
static dictionary m;
// structure node of
// binary tree
class node
{
public int data;
public node left;
public node right;
public node(int data,
node left,
node right)
{
this.data = data;
this.left = left;
this.right = right;
}
};
// function to create a new node
static node newnode(int d)
{
node temp = new node(d, null, null);
// return the created node
return temp;
}
// function that performs the dfs
// traversal on tree to store all the
// nodes at each level in map m
static void dfs(node root, int l)
{
// base case
if (root == null)
return;
// push the current level node
if(!m.containskey(l))
{
arraylist temp = new arraylist();
temp.add(root.data);
m[l] = temp;
}
else
m[l].add(root.data);
// left recursion
dfs(root.left, l 1);
// right recursion
dfs(root.right, l 1);
}
// function that print all the middle
// nodes for each level in binary tree
static void printmidnodes(node root)
{
// stores all node in each level
m = new dictionary();
// perform dfs traversal
dfs(root, 0);
// traverse the map m
foreach (keyvaluepair it in m)
{
// get the size of vector
int size = it.value.count;
// for odd number of elements
if (size % 2 == 1)
{
// print (m/2)th element
console.write(it.value[(size - 1) / 2] "\n");
}
// otherwise
else
{
// print (m/2)th and
// (m/2 1)th element
console.write(it.value[(size - 1) / 2] " "
it.value[((size - 1) / 2) 1] "\n");
}
}
}
// driver code
public static void main(string[] args)
{
/*
binary tree shown below is:
1
/ \
2 3
/ \ / \
4 5 10 8
/ \
11 6
/ \
7 9
*/
// given tree
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(6);
root.left.right.right.left = newnode(7);
root.left.right.right.right = newnode(9);
root.right.left = newnode(10);
root.right.right = newnode(8);
// function call
printmidnodes(root);
}
}
// this code is contributed by pratham76
java 描述语言
output:
1
2 3
5 10
11 6
7 9
时间复杂度:o(n2) 辅助空间: o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
