原文:
给定一棵二叉树。首先打印所有的叶节点，然后从树中移除所有的叶节点，现在打印所有新形成的叶节点，并一直这样做，直到所有的节点都从树中移除。 例:
input :
8
/ \
3 10
/ \ / \
1 6 14 4
/ \
7 13
output :
4 6 7 13 14
1 10
3
8
来源 : 途径:思路是进行简单的 dfs，根据以下条件给每个节点分配不同的值:
- 最初将值为 0 的所有节点赋值。
- 现在，给所有节点赋值为(两个子节点的最大值) 1 。
dfs 之前的树:临时值零被分配给所有节点。
dfs 后的树:节点赋值为(两个子节点的最大值) 1 。
现在，您可以在上面的树中看到，在将所有值分配给每个节点后，任务现在减少到根据分配给它们的节点值的升序来打印树。 以下是上述方法的实施:
c
// c program to print the nodes of binary
// tree as they become the leaf node
#include
using namespace std;
// binary tree node
struct node {
int data;
int order;
struct node* left;
struct node* right;
};
// utility function to allocate a new node
struct node* newnode(int data, int order)
{
struct node* node = new node;
node->data = data;
node->order = order;
node->left = null;
node->right = null;
return (node);
}
// function for postorder traversal of tree and
// assigning values to nodes
void postorder(struct node* node, vector >& v)
{
if (node == null)
return;
/* first recur on left child */
postorder(node->left, v);
/* now recur on right child */
postorder(node->right, v);
// if current node is leaf node, it's order will be 1
if (node->right == null && node->left == null) {
node->order = 1;
// make pair of assigned value and tree value
v.push_back(make_pair(node->order, node->data));
}
else {
// otherwise, the order will be:
// max(left_child_order, right_child_order) 1
node->order = max((node->left)->order, (node->right)->order) 1;
// make pair of assigned value and tree value
v.push_back(make_pair(node->order, node->data));
}
}
// function to print leaf nodes in
// the given order
void printleafnodes(int n, vector >& v)
{
// sort the vector in increasing order of
// assigned node values
sort(v.begin(), v.end());
for (int i = 0; i < n; i ) {
if (v[i].first == v[i 1].first)
cout << v[i].second << " ";
else
cout << v[i].second << "\n";
}
}
// driver code
int main()
{
struct node* root = newnode(8, 0);
root->left = newnode(3, 0);
root->right = newnode(10, 0);
root->left->left = newnode(1, 0);
root->left->right = newnode(6, 0);
root->right->left = newnode(14, 0);
root->right->right = newnode(4, 0);
root->left->left->left = newnode(7, 0);
root->left->left->right = newnode(13, 0);
int n = 9;
vector > v;
postorder(root, v);
printleafnodes(n, v);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print the nodes of binary
// tree as they become the leaf node
import java.util.*;
class gfg
{
// binary tree node
static class node
{
int data;
int order;
node left;
node right;
};
static class pair
{
int first,second;
pair(int a,int b)
{
first = a;
second = b;
}
}
// utility function to allocate a new node
static node newnode(int data, int order)
{
node node = new node();
node.data = data;
node.order = order;
node.left = null;
node.right = null;
return (node);
}
static vector v = new vector();
// function for postorder traversal of tree and
// assigning values to nodes
static void postorder(node node)
{
if (node == null)
return;
/* first recur on left child */
postorder(node.left);
/* now recur on right child */
postorder(node.right);
// if current node is leaf node, it's order will be 1
if (node.right == null && node.left == null)
{
node.order = 1;
// make pair of assigned value and tree value
v.add(new pair(node.order, node.data));
}
else
{
// otherwise, the order will be:
// max(left_child_order, right_child_order) 1
node.order = math.max((node.left).order, (node.right).order) 1;
// make pair of assigned value and tree value
v.add(new pair(node.order, node.data));
}
}
static class sort implements comparator
{
// used for sorting in ascending order of
// roll number
public int compare(pair a, pair b)
{
if(a.first != b.first)
return (a.first - b.first);
else
return (a.second-b.second);
}
}
// function to print leaf nodes in
// the given order
static void printleafnodes(int n)
{
// sort the vector in increasing order of
// assigned node values
collections.sort(v,new sort());
for (int i = 0; i < v.size(); i )
{
if (i != v.size()-1 && v.get(i).first == v.get(i 1).first)
system.out.print( v.get(i).second " ");
else
system.out.print( v.get(i).second "\n");
}
}
// driver code
public static void main(string args[])
{
node root = newnode(8, 0);
root.left = newnode(3, 0);
root.right = newnode(10, 0);
root.left.left = newnode(1, 0);
root.left.right = newnode(6, 0);
root.right.left = newnode(14, 0);
root.right.right = newnode(4, 0);
root.left.left.left = newnode(7, 0);
root.left.left.right = newnode(13, 0);
int n = 9;
postorder(root);
printleafnodes(n);
}
}
// this code is contributed by arnab kundu
python 3
# python3 program to print the nodes of binary
# tree as they become the leaf node
# binary tree node
class newnode:
def __init__(self, data,order):
self.data = data
self.order=order
self.left = none
self.right = none
# function for postorder traversal of tree and
# assigning values to nodes
def postorder(node,v):
if (node == none):
return
""" first recur on left child """
postorder(node.left, v)
""" now recur on right child """
postorder(node.right, v)
# if current node is leaf node,
# it's order will be 1
if (node.right == none and
node.left == none):
node.order = 1
# make pair of assigned value and tree value
v[0].append([node.order, node.data])
else:
# otherwise, the order will be:
# max(left_child_order, right_child_order) 1
node.order = max((node.left).order,
(node.right).order) 1
# make pair of assigned value and tree value
v[0].append([node.order, node.data])
# function to print leaf nodes in
# the given order
def printleafnodes(n, v):
# sort the vector in increasing order of
# assigned node values
v=sorted(v[0])
for i in range(n - 1):
if (v[i][0]== v[i 1][0]):
print(v[i][1], end = " ")
else:
print(v[i][1])
if (v[-1][0]== v[-2][0]):
print(v[-1][1], end = " ")
else:
print(v[-1][1])
# driver code
root = newnode(8, 0)
root.left = newnode(3, 0)
root.right = newnode(10, 0)
root.left.left = newnode(1, 0)
root.left.right = newnode(6, 0)
root.right.left = newnode(14, 0)
root.right.right = newnode(4, 0)
root.left.left.left = newnode(7, 0)
root.left.left.right = newnode(13, 0)
n = 9
v = [[] for i in range(1)]
postorder(root, v)
printleafnodes(n, v)
# this code is contributed by shubhamsingh10
c
// c# program to print the nodes of binary
// tree as they become the leaf node
using system;
using system.collections.generic;
class gfg
{
// binary tree node
public class node
{
public int data;
public int order;
public node left;
public node right;
};
public class pair
{
public int first,second;
public pair(int a,int b)
{
first = a;
second = b;
}
}
// utility function to allocate a new node
static node newnode(int data, int order)
{
node node = new node();
node.data = data;
node.order = order;
node.left = null;
node.right = null;
return (node);
}
static list v = new list();
// function for postorder traversal of
// tree and assigning values to nodes
static void postorder(node node)
{
if (node == null)
return;
/* first recur on left child */
postorder(node.left);
/* now recur on right child */
postorder(node.right);
// if current node is leaf node,
// it's order will be 1
if (node.right == null &&
node.left == null)
{
node.order = 1;
// make pair of assigned value
// and tree value
v.add(new pair(node.order, node.data));
}
else
{
// otherwise, the order will be:
// max(left_child_order,
// right_child_order) 1
node.order = math.max((node.left).order,
(node.right).order) 1;
// make pair of assigned value
// and tree value
v.add(new pair(node.order, node.data));
}
}
// used for sorting in ascending order
// of roll number
public static int compare(pair a, pair b)
{
if(a.first != b.first)
return (a.first - b.first);
else
return (a.second - b.second);
}
// function to print leaf nodes in
// the given order
static void printleafnodes(int n)
{
// sort the list in increasing order
// of assigned node values
v.sort(compare);
for (int i = 0; i < v.count; i )
{
if (i != v.count - 1 &&
v[i].first == v[i 1].first)
console.write(v[i].second " ");
else
console.write(v[i].second "\n");
}
}
// driver code
public static void main(string[] args)
{
node root = newnode(8, 0);
root.left = newnode(3, 0);
root.right = newnode(10, 0);
root.left.left = newnode(1, 0);
root.left.right = newnode(6, 0);
root.right.left = newnode(14, 0);
root.right.right = newnode(4, 0);
root.left.left.left = newnode(7, 0);
root.left.left.right = newnode(13, 0);
int n = 9;
postorder(root);
printleafnodes(n);
}
}
// this code is contributed
// by arnab kundu
java 描述语言
output:
4 6 7 13 14
1 10
3
8
时间复杂度 : o(nlogn) 辅助空间 : o(n)，其中 n 是给定二叉树中的节点数。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
