Рубрики

Найти количество отдельных оцененных поддеревьев

Учитывая двоичное дерево, напишите программу для подсчета количества однозначных поддеревьев. Однозначное поддерево — это то, в котором все узлы имеют одинаковое значение. Ожидаемая сложность времени O (n).

Пример:

Input: root of below tree
              5
             / \
            1   5
           / \   \
          5   5   5
Output: 4
There are 4 subtrees with single values.


Input: root of below tree
              5
             / \
            4   5
           / \   \
          4   4   5                
Output: 5
There are five subtrees with single values.

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Простое решение — пройти через дерево. Для каждого пройденного узла проверьте, все ли значения в этом узле одинаковы или нет. Если то же самое, то увеличить счетчик. Временная сложность этого решения составляет O (n 2 ).

Эффективным решением является обход дерева снизу вверх. Для каждого посещенного поддерева верните значение true, если поддерево, корни которого находятся под ним, имеют одно значение и число приращений. Поэтому идея состоит в том, чтобы использовать count в качестве ссылочного параметра в рекурсивных вызовах и использовать возвращаемые значения, чтобы выяснить, являются ли левые и правые поддеревья однозначными или нет.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска количества однозначных поддеревьев
#include<bits/stdc++.h>

using namespace std;

  
// Узел дерева

struct Node

{

    int data;

    struct Node* left, *right;

};

  
// Сервисная функция для создания нового узла

Node* newNode(int data)

{

    Node* temp = new Node;

    temp->data = data;

    temp->left = temp->right = NULL;

    return (temp);

}

  
// Эта функция увеличивает количество на единицу
// ценные поддеревья под корнем. Возвращает true, если поддерево
// под корнем - Singly, иначе false.

bool countSingleRec(Node* root, int &count)

{

    // Возвращаем false, чтобы указать NULL

    if (root == NULL)

       return true;

  

    // Рекурсивно подсчитываем также в левом и правом поддеревьях

    bool left = countSingleRec(root->left, count);

    bool right = countSingleRec(root->right, count);

  

    // Если любое из поддеревьев не является одиночным, то это

    // не может быть в одиночку.

    if (left == false || right == false)

       return false;

  

    // Если левое поддерево одиночное и непустое, но данные

    // не соответствует

    if (root->left && root->data != root->left->data)

        return false;

  

    // То же самое для правого поддерева

    if (root->right && root->data != root->right->data)

        return false;

  

    // Если ни одно из вышеприведенных условий не выполняется, то

    // дерево с корнем под корнем однозначно, приращение

    // посчитаем и вернем истину.

    count++;

    return true;

}

  
// Эта функция в основном вызывает countSingleRec ()
// после инициализации считать как 0

int countSingle(Node* root)

{

    // Инициализировать результат

    int count = 0;

  

    // Рекурсивная функция для подсчета

    countSingleRec(root, count);

  

    return count;

}

  
// Программа драйвера для тестирования

int main()

{

    / * Построим дерево ниже

            5

          / /

        4 5

      ///

     4 4 5 * /

    Node* root        = newNode(5);

    root->left        = newNode(4);

    root->right       = newNode(5);

    root->left->left  = newNode(4);

    root->left->right = newNode(4);

    root->right->right = newNode(5);

  

    cout << "Count of Single Valued Subtrees is "

         << countSingle(root);

    return 0;

}

Джава

// Java программа для поиска количества однозначных поддеревьев

   
/ * Класс, содержащий левого и правого потомка текущего

 значение узла и ключа * /

class Node 

{

    int data;

    Node left, right;

   

    public Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class Count 

{

    int count = 0;

}

   

class BinaryTree 

{

    Node root;  

    Count ct = new Count();

       

    // Эта функция увеличивает количество на единицу

    // ценные поддеревья под корнем. Возвращает true, если поддерево

    // под корнем - Singly, иначе false.

    boolean countSingleRec(Node node, Count c) 

    {

        // Возвращаем false, чтобы указать NULL

        if (node == null)

            return true;

           

        // Рекурсивно подсчитываем также в левом и правом поддеревьях

        boolean left = countSingleRec(node.left, c);

        boolean right = countSingleRec(node.right, c);

   

        // Если любое из поддеревьев не является одиночным, то это

        // не может быть в одиночку.

        if (left == false || right == false)

            return false;

   

        // Если левое поддерево одиночное и непустое, но данные

        // не соответствует

        if (node.left != null && node.data != node.left.data)

            return false;

   

        // То же самое для правого поддерева

        if (node.right != null && node.data != node.right.data)

            return false;

   

        // Если ни одно из вышеприведенных условий не выполняется, то

        // дерево с корнем под корнем однозначно, приращение

        // посчитаем и вернем истину.

        c.count++;

        return true;

    }

   

    // Эта функция в основном вызывает countSingleRec ()

    // после инициализации считать как 0

    int countSingle() 

    {

        return countSingle(root);

    }

   

    int countSingle(Node node) 

    {

        // Рекурсивная функция для подсчета

        countSingleRec(node, ct);

        return ct.count;

    }

   

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[]) 

    {

           / * Построим дерево ниже

                5

              / /

            4 5

          ///

         4 4 5 * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(5);

        tree.root.left = new Node(4);

        tree.root.right = new Node(5);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(4);

        tree.root.right.right = new Node(5);

   

        System.out.println("The count of single valued sub trees is : "

                                            + tree.countSingle());

    }

}

   
// Этот код предоставлен Mayank Jaiswal

питон

# Программа Python для поиска количества однозначных поддеревьев

  
# Структура узла

class Node:

    # Сервисная функция для создания нового узла

    def __init__(self ,data):

        self.data = data

        self.left = None 

        self.right = None

  

  
# Эта функция увеличивает количество на число одиночных
# значимые поддеревья под корнем. Возвращает true, если поддерево
# под корнем - Singly, иначе false.

def countSingleRec(root , count):

    # Вернуть False, чтобы указать None

    if root is None :

        return True

  

    # Рекурсивно считать в левом и правом субтрессе также

    left = countSingleRec(root.left , count)

    right = countSingleRec(root.right , count)

      

    # Если какой-либо из субтресс не является одиночным, то это

    # нельзя поодиночке

    if left == False or right  == False :

        return False 

      

    # Если левое поддерево одиночное и не пустое, но данные

    # не соответствует

    if root.left and root.data != root.left.data:

        return False

  

    # то же самое для правого поддерева

    if root.right and root.data != root.right.data:

        return False

  

    # Если ни одно из вышеперечисленных условий не выполняется

    # дерево с корнем под корнем однозначно, приращение

    # считать и возвращать true

    count[0] += 1

    return True 

  

  
# Эта функция в основном calss countSingleRec ()
# после инициализации считать как 0

def countSingle(root):

    # инициализировать результат

    count = [0]

  

    # Рекурсивная функция для подсчета

    countSingleRec(root , count)

  

    return count[0]

  

  
# Драйвер программы для тестирования

  
"" "Давайте построим дерево ниже

            5

          / /

        4 5

       ///

      4 4 5

«»»

root = Node(5)

root.left = Node(4)

root.right = Node(5)

root.left.left = Node(4)

root.left.right = Node(4)

root.right.right = Node(5)

countSingle(root)

print "Count of Single Valued Subtress is" , countSingle(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

  
// C # программа для поиска количества однозначных поддеревьев

  
/ * Класс, содержащий левого и правого потомка текущего

 значение узла и ключа * /

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class Count

{

    public int count = 0;

}

  

public class BinaryTree

{

    public Node root;

    public Count ct = new Count();

  

    // Эта функция увеличивает количество на единицу

    // ценные поддеревья под корнем. Возвращает true, если поддерево

    // под корнем - Singly, иначе false.

    public virtual bool countSingleRec(Node node, Count c)

    {

        // Возвращаем false, чтобы указать NULL

        if (node == null)

        {

            return true;

        }

  

        // Рекурсивно подсчитываем также в левом и правом поддеревьях

        bool left = countSingleRec(node.left, c);

        bool right = countSingleRec(node.right, c);

  

        // Если любое из поддеревьев не является одиночным, то это

        // не может быть в одиночку.

        if (left == false || right == false)

        {

            return false;

        }

  

        // Если левое поддерево одиночное и непустое, но данные

        // не соответствует

        if (node.left != null && node.data != node.left.data)

        {

            return false;

        }

  

        // То же самое для правого поддерева

        if (node.right != null && node.data != node.right.data)

        {

            return false;

        }

  

        // Если ни одно из вышеприведенных условий не выполняется, то

        // дерево с корнем под корнем однозначно, приращение

        // посчитаем и вернем истину.

        c.count++;

        return true;

    }

  

    // Эта функция в основном вызывает countSingleRec ()

    // после инициализации считать как 0

    public virtual int countSingle()

    {

        return countSingle(root);

    }

  

    public virtual int countSingle(Node node)

    {

        // Рекурсивная функция для подсчета

        countSingleRec(node, ct);

        return ct.count;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void Main(string[] args)

    {

           / * Построим дерево ниже

                5

              / /

            4 5

          ///

         4 4 5 * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(5);

        tree.root.left = new Node(4);

        tree.root.right = new Node(5);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(4);

        tree.root.right.right = new Node(5);

  

        Console.WriteLine("The count of single valued sub trees is : " + tree.countSingle());

    }

}

  

  // Этот код предоставлен Shrikant13


Выход:

Count of Single Valued Subtrees is 5

Временная сложность этого решения составляет O (n), где n — количество узлов в данном двоичном дереве.

Спасибо Gaurav Ahirwar за предложенное выше решение.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти количество отдельных оцененных поддеревьев

0.00 (0%) 0 votes