原文:
给定一棵二叉树和一个整数值 k，任务是在给定的二叉树中找到所有节点，这些节点在以它们为根的子树中有 k 个叶子。
例:
// for above binary tree
input : k = 2
output: {3}
// here node 3 have k = 2 leaves
input : k = 1
output: {6}
// here node 6 have k = 1 leave
这里任何有 k 个叶子的节点都意味着左子树和右子树的叶子之和必须等于 k，所以我们用树的后序遍历来解决这个问题。首先我们计算左边子树的叶子，然后计算右边子树的叶子，如果和等于 k，那么打印当前节点。在每次递归调用中，我们将左子树和右子树的叶子的和返回给它的祖先。 以下是上述方法的实施:
c
// c program to count all nodes having k leaves
// in subtree rooted with them
#include
using namespace std;
/* a binary tree node */
struct node
{
int data ;
struct node * left, * right ;
};
/* helper function that allocates a new node with the
given data and null left and right pointers. */
struct node * newnode(int data)
{
struct node * node = new node;
node->data = data;
node->left = node->right = null;
return (node);
}
// function to print all nodes having k leaves
int kleaves(struct node *ptr,int k)
{
// base conditions : no leaves
if (ptr == null)
return 0;
// if node is leaf
if (ptr->left == null && ptr->right == null)
return 1;
// total leaves in subtree rooted with this
// node
int total = kleaves(ptr->left, k)
kleaves(ptr->right, k);
// print this node if total is k
if (k == total)
cout << ptr->data << " ";
return total;
}
// driver program to run the case
int main()
{
struct node *root = newnode(1);
root->left = newnode(2);
root->right = newnode(4);
root->left->left = newnode(5);
root->left->right = newnode(6);
root->left->left->left = newnode(9);
root->left->left->right = newnode(10);
root->right->right = newnode(8);
root->right->left = newnode(7);
root->right->left->left = newnode(11);
root->right->left->right = newnode(12);
kleaves(root, 2);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to count all nodes having k leaves
// in subtree rooted with them
class gfg {
/* a binary tree node */
static class node
{
int data ;
node left, right ;
node(int data)
{
this.data = data;
}
node()
{
}
}
/* helper function that allocates a new node with the
given data and null left and right pointers. */
static node newnode(int data)
{
node node = new node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// function to print all nodes having k leaves
static int kleaves(node ptr,int k)
{
// base conditions : no leaves
if (ptr == null)
return 0;
// if node is leaf
if (ptr.left == null && ptr.right == null)
return 1;
// total leaves in subtree rooted with this
// node
int total = kleaves(ptr.left, k) kleaves(ptr.right, k);
// print this node if total is k
if (k == total)
system.out.print(ptr.data " ");
return total;
}
// driver program to run the case
public static void main(string[] args)
{
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(4);
root.left.left = newnode(5);
root.left.right = newnode(6);
root.left.left.left = newnode(9);
root.left.left.right = newnode(10);
root.right.right = newnode(8);
root.right.left = newnode(7);
root.right.left.left = newnode(11);
root.right.left.right = newnode(12);
kleaves(root, 2);
}
}
python 3
# python3 program to count all nodes
# having k leaves in subtree rooted with them
# a binary tree node has data, pointer to
# left child and a pointer to right child
# helper function that allocates a new node
# with the given data and none left and
# right pointers
class newnode:
def __init__(self, data):
self.data = data
self.left = none
self.right = none
# function to print all nodes having k leaves
def kleaves(ptr, k):
# base conditions : no leaves
if (ptr == none):
return 0
# if node is leaf
if (ptr.left == none and
ptr.right == none):
return 1
# total leaves in subtree rooted with this
# node
total = kleaves(ptr.left, k) \
kleaves(ptr.right, k)
# prthis node if total is k
if (k == total):
print(ptr.data, end = " ")
return total
# driver code
root = newnode(1)
root.left = newnode(2)
root.right = newnode(4)
root.left.left = newnode(5)
root.left.right = newnode(6)
root.left.left.left = newnode(9)
root.left.left.right = newnode(10)
root.right.right = newnode(8)
root.right.left = newnode(7)
root.right.left.left = newnode(11)
root.right.left.right = newnode(12)
kleaves(root, 2)
# this code is contributed by shubhamsingh10
c
// c# program to count all nodes having k leaves
// in subtree rooted with them
using system;
class gfg
{
/* a binary tree node */
public class node
{
public int data ;
public node left, right ;
public node(int data)
{
this.data = data;
}
public node()
{
}
}
/* helper function that allocates a new node with the
given data and null left and right pointers. */
static node newnode(int data)
{
node node = new node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// function to print all nodes having k leaves
static int kleaves(node ptr,int k)
{
// base conditions : no leaves
if (ptr == null)
return 0;
// if node is leaf
if (ptr.left == null && ptr.right == null)
return 1;
// total leaves in subtree rooted with this
// node
int total = kleaves(ptr.left, k) kleaves(ptr.right, k);
// print this node if total is k
if (k == total)
console.write(ptr.data " ");
return total;
}
// driver program to run the case
public static void main(string[] args)
{
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(4);
root.left.left = newnode(5);
root.left.right = newnode(6);
root.left.left.left = newnode(9);
root.left.left.right = newnode(10);
root.right.right = newnode(8);
root.right.left = newnode(7);
root.right.left.left = newnode(11);
root.right.left.right = newnode(12);
kleaves(root, 2);
}
}
// this code has been contributed by 29ajaykumar
java 描述语言
输出:
5 7
时间复杂度: o(n)
本文由 供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
