原文:
给定一个表示二进制堆的的叶节点。
示例:
input:
arr[] = {1, 2, 3, 4, 5, 6, 7}
output: 4 5 6 7
explanation:
1
/ \
2 3
/ \ / \
4 5 6 7
leaf nodes of the binary heap are:
4 5 6 7
input:
arr[] = {1, 2, 3, 4, 5,
6, 7, 8, 9, 10}
output: 6 7 8 9 10
explanation:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
leaf nodes of the binary heap are:
6 7 8 9 10
方法:问题中的关键观察是，如果 h 是二进制堆的高度，那么二进制堆的每个叶节点都将处于高度 h 或 h -1，处。因此，叶节点可以计算如下:
- 计算二进制堆的总
- 以相反的顺序遍历数组，并将每个节点的高度与二进制堆的计算高度 h 进行比较。
- 如果当前节点的高度是 h，则将当前节点添加到叶节点。
- 否则，如果当前节点的高度为 h-1，并且没有子节点，那么也将该节点添加为叶节点。
下面是上述方法的实现:
java 语言(一种计算机语言，尤用于创建网站)
// java implementation to print
// the leaf nodes of a binary heap
import java.lang.*;
import java.util.*;
class gfg {
// function to calculate height
// of the binary heap with given
// the count of the nodes
static int height(int n)
{
return (int)math.ceil(
math.log(n 1)
/ math.log(2))
- 1;
}
// function to find the leaf
// nodes of binary heap
static void findleafnodes(
int arr[], int n)
{
// calculate the height of
// the complete binary tree
int h = height(n);
arraylist arrlist
= new arraylist<>();
for (int i = n - 1; i >= 0; i--) {
if (height(i 1) == h) {
arrlist.add(arr[i]);
}
else if (height(i 1) == h - 1
&& n <= ((2 * i) 1)) {
// if the height if h-1,
// then there should not
// be any child nodes
arrlist.add(arr[i]);
}
else {
break;
}
}
printleafnodes(arrlist);
}
// function to print the leaf nodes
static void printleafnodes(
arraylist arrlist)
{
for (int i = arrlist.size() - 1;
i >= 0; i--) {
system.out.print(
arrlist.get(i) " ");
}
}
// driver code
public static void main(string[] args)
{
int arr[] = { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 };
findleafnodes(arr, arr.length);
}
}
c
// c# implementation to print
// the leaf nodes of a binary heap
using system;
using system.collections.generic;
class gfg{
// function to calculate height
// of the binary heap with given
// the count of the nodes
static int height(int n)
{
return (int)math.ceiling(
math.log(n 1) /
math.log(2)) - 1;
}
// function to find the leaf
// nodes of binary heap
static void findleafnodes(int []arr,
int n)
{
// calculate the height of
// the complete binary tree
int h = height(n);
list arrlist = new list();
for (int i = n - 1; i >= 0; i--)
{
if (height(i 1) == h)
{
arrlist.add(arr[i]);
}
else if (height(i 1) == h - 1 &&
n <= ((2 * i) 1))
{
// if the height if h-1,
// then there should not
// be any child nodes
arrlist.add(arr[i]);
}
else
{
break;
}
}
printleafnodes(arrlist);
}
// function to print the leaf nodes
static void printleafnodes(list arrlist)
{
for (int i = arrlist.count - 1; i >= 0; i--)
{
console.write(arrlist[i] " ");
}
}
// driver code
public static void main(string[] args)
{
int []arr = { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 };
findleafnodes(arr, arr.length);
}
}
// this code is contributed by princi singh
output:
6 7 8 9 10
性能分析:
- 时间复杂度: o(l)，其中 l 为叶节点数。
- 辅助空间: o(1)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
