Подсчитайте узлы с двумя дочерними элементами на уровне L в двоичном дереве

Опубликовано: 23 Января, 2022

Учитывая двоичное дерево, задача состоит в том, чтобы подсчитать количество узлов с двумя дочерними элементами на заданном уровне L.
Примеры:

 Вход: 
          1
         / 
        2 3
       /  
      4 5 6
         / / 
        7 8 9
L = 2
Выход: 1

Вход:
          20
         / 
        8 22
       /  / 
      5 3 4 25
     /  /  
    1 10 2 14 6
L = 3
Выход: 2
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: инициализировать переменную count = 0 . Рекурсивно перемещаться по дереву в порядке уровней. Если текущий уровень совпадает с заданным, проверьте, есть ли у текущего узла два дочерних элемента. Если у него два дочерних элемента, увеличьте счетчик переменных.

Below is the implementation of the above approach: 

C++

// C++ program to find number of full nodes
// at a given level
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree node
struct Node {
    int data;
    struct Node *left, *right;
};
 
// Utility function to allocate memory for a new node
struct Node* newNode(int data)
{
    struct Node* node = new (struct Node);
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
 
// Function that returns the height of binary tree
int height(struct Node* root)
{
    if (root == NULL)
        return 0;
 
    int lheight = height(root->left);
    int rheight = height(root->right);
 
    return max(lheight, rheight) + 1;
}
 
// Level Order traversal to find the number of nodes
// having two children
void LevelOrder(struct Node* root, int level, int& count)
{
    if (root == NULL)
        return;
 
    if (level == 1 && root->left && root->right)
        count++;
 
    else if (level > 1) {
        LevelOrder(root->left, level - 1, count);
        LevelOrder(root->right, level - 1, count);
    }
}
 
// Returns the number of full nodes
// at a given level
int CountFullNodes(struct Node* root, int L)
{
    // Stores height of tree
    int h = height(root);
 
    // Stores count of nodes at a given level
    // that have two children
    int count = 0;
 
    LevelOrder(root, L, count);
 
    return count;
}
 
// Driver code
int main()
{
    struct Node* root = newNode(7);
    root->left = newNode(5);
    root->right = newNode(6);
    root->left->left = newNode(8);
    root->left->right = newNode(1);
    root->left->left->left = newNode(2);
    root->left->left->right = newNode(11);
    root->right->left = newNode(3);
    root->right->right = newNode(9);
    root->right->right->right = newNode(13);
    root->right->right->left = newNode(10);
    root->right->right->right->left = newNode(4);
    root->right->right->right->right = newNode(12);
 
    int L = 3;
 
    cout << CountFullNodes(root, L);
 
    return 0;
}

Java

// Java program to find number of full nodes
// at a given level
class GFG
{
 
//INT class
static class INT
{
    int a;
}
 
// A binary tree node
static class Node
{
    int data;
    Node left, right;
};
 
// Utility function to allocate memory for a new node
static Node newNode(int data)
{
    Node node = new Node();
    node.data = data;
    node.left = node.right = null;
    return (node);
}
 
// Function that returns the height of binary tree
static int height(Node root)
{
    if (root == null)
        return 0;
 
    int lheight = height(root.left);
    int rheight = height(root.right);
 
    return Math.max(lheight, rheight) + 1;
}
 
// Level Order traversal to find the number of nodes
// having two children
static void LevelOrder( Node root, int level, INT count)
{
    if (root == null)
        return;
 
    if (level == 1 && root.left!=null && root.right!=null)
        count.a++;
 
    else if (level > 1)
    {
        LevelOrder(root.left, level - 1, count);
        LevelOrder(root.right, level - 1, count);
    }
}
 
// Returns the number of full nodes
// at a given level
static int CountFullNodes( Node root, int L)
{
    // Stores height of tree
    int h = height(root);
 
    // Stores count of nodes at a given level
    // that have two children
    INT count =new INT();
    count.a = 0;
 
    LevelOrder(root, L, count);
 
    return count.a;
}
 
// Driver code
public static void main(String args[])
{
    Node root = newNode(7);
    root.left = newNode(5);
    root.right = newNode(6);
    root.left.left = newNode(8);
    root.left.right = newNode(1);
    root.left.left.left = newNode(2);
    root.left.left.right = newNode(11);
    root.right.left = newNode(3);
    root.right.right = newNode(9);
    root.right.right.right = newNode(13);
    root.right.right.left = newNode(10);
    root.right.right.right.left = newNode(4);
    root.right.right.right.right = newNode(12);
 
    int L = 3;
 
    System.out.print( CountFullNodes(root, L));
 
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to find number of
# full nodes at a given level
 
# INT class
class INT:
  
    def __init__(self):
         
        self.a = 0
 
# A binary tree node
class Node:
     
    def __init__(self, data):
         
        self.left = None
        self.right = None
        self.data = data
  
# Utility function to allocate
# memory for a new node
def newNode(data):
 
    node = Node(data)
     
    return node
 
# Function that returns the
# height of binary tree
def height(root):
 
    if (root == None):
        return 0;
  
    lheight = height(root.left);
    rheight = height(root.right);
  
    return max(lheight, rheight) + 1;
 
# Level Order traversal to find the
# number of nodes having two children
def LevelOrder(root, level, count):
 
    if (root == None):
        return;
  
    if (level == 1 and
        root.left != None and
       root.right != None):
        count.a += 1
  
    elif (level > 1):
        LevelOrder(root.left,
                   level - 1, count);
        LevelOrder(root.right,
                   level - 1, count);
  
# Returns the number of full nodes
# at a given level
def CountFullNodes(root, L):
 
    # Stores height of tree
    h = height(root);
  
    # Stores count of nodes at a
    # given level that have two children
    count = INT()
  
    LevelOrder(root, L, count);
  
    return count.a
 
# Driver code   
if __name__=="__main__":
     
    root = newNode(7);
    root.left = newNode(5);
    root.right = newNode(6);
    root.left.left = newNode(8);
    root.left.right = newNode(1);
    root.left.left.left = newNode(2);
    root.left.left.right = newNode(11);
    root.right.left = newNode(3);
    root.right.right = newNode(9);
    root.right.right.right = newNode(13);
    root.right.right.left = newNode(10);
    root.right.right.right.left = newNode(4);
    root.right.right.right.right = newNode(12);
  
    L = 3;
  
    print(CountFullNodes(root, L))
     
# This code is contributed by rutvik_56

C#

// C# program to find number of full nodes
// at a given level
using System;
 
class GFG
{
 
// INT class
public class INT
{
    public int a;
}
 
// A binary tree node
public class Node
{
    public int data;
    public Node left, right;
};
 
// Utility function to allocate memory for a new node
static Node newNode(int data)
{
    Node node = new Node();
    node.data = data;
    node.left = node.right = null;
    return (node);
}
 
// Function that returns the height of binary tree
static int height(Node root)
{
    if (root == null)
        return 0;
 
    int lheight = height(root.left);
    int rheight = height(root.right);
 
    return Math.Max(lheight, rheight) + 1;
}
 
// Level Order traversal to find the number of nodes
// having two children
static void LevelOrder( Node root, int level, INT count)
{
    if (root == null)
        return;
 
    if (level == 1 && root.left!=null && root.right!=null)
        count.a++;
 
    else if (level > 1)
    {
        LevelOrder(root.left, level - 1, count);
        LevelOrder(root.right, level - 1, count);
    }
}
 
// Returns the number of full nodes
// at a given level
static int CountFullNodes( Node root, int L)
{
    // Stores height of tree
    int h = height(root);
 
    // Stores count of nodes at a given level
    // that have two children
    INT count =new INT();
    count.a = 0;
 
    LevelOrder(root, L, count);
 
    return count.a;
}
 
// Driver code
public static void Main(String []args)
{
    Node root = newNode(7);
    root.left = newNode(5);
    root.right = newNode(6);
    root.left.left = newNode(8);
    root.left.right = newNode(1);
    root.left.left.left = newNode(2);
    root.left.left.right = newNode(11);
    root.right.left = newNode(3);
    root.right.right = newNode(9);
    root.right.right.right = newNode(13);
    root.right.right.left = newNode(10);
    root.right.right.right.left = newNode(4);
    root.right.right.right.right = newNode(12);
 
    int L = 3;
 
    Console.Write( CountFullNodes(root, L));
 
}
}
 
// This code has been contributed by 29AjayKumar
Output: 
2

 

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022