Dado un árbol binario y un valor entero K, la tarea es encontrar todos los Nodes en el árbol binario dado que tengan K hojas en el subárbol enraizado con ellos.
C++
// C++ program to count all nodes having k leaves
// in subtree rooted with them
#include<bits/stdc++.h>
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);
}
}
Python3
# 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) # Print this 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
Javascript
<script>
// Javascript program to count all nodes having k leaves
// in subtree rooted with them
/* A binary tree node */
class Node
{
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
constructor(data)
{
this.data = data;
this.left=this.right=null;
}
}
// Function to print all nodes having k leaves
function kLeaves(ptr,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
let total = kLeaves(ptr.left, k) + kLeaves(ptr.right, k);
// Print this node if total is k
if (k == total)
document.write(ptr.data + " ");
return total;
}
// Driver program to run the case
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(4);
root.left.left = new Node(5);
root.left.right = new Node(6);
root.left.left.left = new Node(9);
root.left.left.right = new Node(10);
root.right.right = new Node(8);
root.right.left = new Node(7);
root.right.left.left = new Node(11);
root.right.left.right = new Node(12);
kLeaves(root, 2);
// This code is contributed by rag2127
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA