Рубрики

Найти умножение сумм данных листьев на тех же уровнях

Если задано двоичное дерево, верните для него следующее значение.
1) Для каждого уровня вычислите сумму всех листьев, если на этом уровне есть листья. В противном случае игнорируйте это.
2) Вернуть умножение всех сумм.

Примеры:

Input: Root of below tree
         2
       /   \
      7     5
             \
              9
Output: 63
First levels doesn't have leaves. Second level
has one leaf 7 and third level also has one 
leaf 9.  Therefore result is 7*9 = 63


Input: Root of below tree
         2
       /   \
     7      5
    / \      \
   8   6      9
      / \    /  \
     1  11  4    10 

Output: 208
First two levels don't have leaves. Third
level has single leaf 8. Last level has four
leaves 1, 11, 4 and 10. Therefore result is 
8 * (1 + 11 + 4 + 10)  

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

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

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

C ++

/ * Итеративная программа C ++ для поиска суммы данных всех листов

   двоичного дерева на том же уровне, а затем умножить суммы

   получается всех уровней. * /

#include <bits/stdc++.h>

using namespace std;

  
// Узел двоичного дерева

struct Node {

    int data;

    struct Node *left, *right;

};

  
// вспомогательная функция для проверки, является ли Node листом дерева

bool isLeaf(Node* root)

{

    return (!root->left && !root->right);

}

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

   умножение сумм * /

int sumAndMultiplyLevelData(Node* root)

{

    // Дерево пусто

    if (!root)

        return 0;

  

    int mul = 1; / * Для сохранения результата * /

  

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

    queue<Node*> q;

  

    // ставим в очередь Root и инициализируем высоту

    q.push(root);

  

    // Выполнить обход уровня дерева

    while (1) {

        // NodeCount (размер очереди) указывает количество узлов

        // на текущем уровне.

        int NodeCount = q.size();

  

        // Если на текущем уровне нет узлов, мы закончили

        if (NodeCount == 0)

            break;

  

        // Инициализируем листовую сумму для текущего уровня

        int levelSum = 0;

  

        // Булева переменная, указывающая, найден ли лист

        // Узел на текущем уровне или нет

        bool leafFound = false;

  

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

        // Узлы следующего уровня

        while (NodeCount > 0) {

            // Обработка следующего узла текущего уровня

            Node* Node = q.front();

  

            / * если Node это лист, обновлять сумму на уровне * /

            if (isLeaf(Node)) {

                leafFound = true;

                levelSum += Node->data;

            }

            q.pop();

  

            // Добавляем дочерних узлов

            if (Node->left != NULL)

                q.push(Node->left);

            if (Node->right != NULL)

                q.push(Node->right);

            NodeCount--;

        }

  

        // Если мы нашли хотя бы один лист, мы умножаем

        // результат с суммой уровня.

        if (leafFound)

            mul *= levelSum;

    }

  

    return mul; // Возвращаем результат

}

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

Node* newNode(int data)

{

    Node* temp = new Node;

    temp->data = data;

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

    return temp;

}

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

int main()

{

    Node* root = newNode(2);

    root->left = newNode(7);

    root->right = newNode(5);

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

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

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

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

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

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

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

  

    cout << "Final product value = "

         << sumAndMultiplyLevelData(root) << endl;

  

    return 0;

}

Джава

/ * Итеративная Java-программа для поиска суммы данных всех листьев

   двоичного дерева на том же уровне, а затем умножить суммы

   получается всех уровней. * /

  
/ * импортируем необходимый класс * /

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

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

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

class Node {

  

    int data;

    Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class BinaryTree {

  

    Node root;

  

    // вспомогательная функция для проверки, является ли Node листом дерева

    boolean isLeaf(Node node)

    {

        return ((node.left == null) && (node.right == null));

    }

  

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

     умножение сумм * /

    int sumAndMultiplyLevelData()

    {

        return sumAndMultiplyLevelData(root);

    }

    int sumAndMultiplyLevelData(Node node)

    {

        // Дерево пусто

        if (node == null) {

            return 0;

        }

  

        int mul = 1; / * Для сохранения результата * /

  

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

        LinkedList<Node> q = new LinkedList<Node>();

  

        // ставим в очередь Root и инициализируем высоту

        q.add(node);

  

        // Выполнить обход уровня дерева

        while (true) {

  

            // NodeCount (размер очереди) указывает количество узлов

            // на текущем уровне.

            int NodeCount = q.size();

  

            // Если на текущем уровне нет узлов, мы закончили

            if (NodeCount == 0) {

                break;

            }

  

            // Инициализируем листовую сумму для текущего уровня

            int levelSum = 0;

  

            // Булева переменная, указывающая, найден ли лист

            // Узел на текущем уровне или нет

            boolean leafFound = false;

  

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

            // Узлы следующего уровня

            while (NodeCount > 0) {

                Node node1;

                node1 = q.poll();

  

                / * если Node это лист, обновлять сумму на уровне * /

                if (isLeaf(node1)) {

                    leafFound = true;

                    levelSum += node1.data;

                }

  

                // Добавляем дочерних узлов

                if (node1.left != null) {

                    q.add(node1.left);

                }

                if (node1.right != null) {

                    q.add(node1.right);

                }

                NodeCount--;

            }

  

            // Если мы нашли хотя бы один лист, мы умножаем

            // результат с суммой уровня.

            if (leafFound) {

                mul *= levelSum;

            }

        }

  

        return mul; // Возвращаем результат

    }

  

    public static void main(String args[])

    {

  

        / * создание бинарного дерева и ввод

         узлы * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(2);

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

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

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

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

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

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

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

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

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

        System.out.println("The final product value : "

                           + tree.sumAndMultiplyLevelData());

    }

}

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

python3

"" "Итеративная программа Python3 для поиска
сумма данных всех листьев двоичного файла
дерево на том же уровне, а затем умножить
суммы, полученные на всех уровнях.

  
# Узел двоичного дерева
# Сервисная функция для создания
# Новый узел дерева

class newNode: 

    def __init__(self, data): 

        self.data = data 

        self.left = self.right = None

          
# вспомогательная функция для проверки, если
# Узел - это лист дерева

def isLeaf(root) :

  

    return (not root.left and 

            not root.right) 

  
"" "Рассчитать сумму всех листовых узлов на каждом
уровень и возвращает умножение сумм "" "

def sumAndMultiplyLevelData( root) :

  

    # Дерево пусто

    if (not root) :

        return 0

  

    mul = 1

      

    "" "Сохранить результат" ""

    # Создать пустую очередь для уровня

    # заказ тарверсала

    q = []

  

    # Поставить в очередь Root и инициализировать высоту

    q.append(root) 

  

    # Выполнить обход уровня дерева

    while (1):

          

        # NodeCount (размер очереди) указывает

        # количество узлов на текущем уровне.

        NodeCount = len(q) 

  

        # Если в данный момент нет узлов

        # уровень, мы сделали

        if (NodeCount == 0) :

            break

  

        # Инициализировать листовую сумму для

        # текущий уровень

        levelSum = 0

  

        # Булева переменная для указания

        # если найден листовой узел на текущий

        # уровень или нет

        leafFound = False

  

        # Удалить все узлы текущего уровня

        # и поставить в очередь все узлы следующего уровня

        while (NodeCount > 0) :

              

            # Обработка следующего узла текущего уровня

            Node = q[0

  

            "" "если Node - это лист, обновите

                сумма на уровне "" "

            if (isLeaf(Node)) :

                leafFound = True

                levelSum += Node.data 

  

            q.pop(0

  

            # Добавить детей из узла

            if (Node.left != None) :

                q.append(Node.left) 

            if (Node.right != None) :

                q.append(Node.right) 

            NodeCount-=1

                  

        # Если мы нашли хотя бы один лист,

        # умножаем результат на сумму уровня.

        if (leafFound) :

            mul *= levelSum 

      

    return mul # Вернуть результат

  
Код водителя

if __name__ == '__main__':

    root = newNode(2

    root.left = newNode(7

    root.right = newNode(5

    root.left.right = newNode(6

    root.left.left = newNode(8

    root.left.right.left = newNode(1

    root.left.right.right = newNode(11

    root.right.right = newNode(9

    root.right.right.left = newNode(4

    root.right.right.right = newNode(10

  

    print("Final product value = ",

           sumAndMultiplyLevelData(root)) 

  
# Этот код добавлен
# от SHUBHAMSINGH10

C #

/ * Итеративная C # программа для поиска суммы
данных всех листьев двоичного дерева
на том же уровне, а затем умножить суммы
получается всех уровней. * /

  
/ * импортируем необходимый класс * /

using System;

using System.Collections.Generic;

  
/ * Класс, содержащий левого и правого ребенка

 текущего узла и значения ключа * /

public class Node 

{

  

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree 

{

  

    Node root;

  

    // вспомогательная функция для проверки

    // Узел - это лист дерева

    bool isLeaf(Node node)

    {

        return ((node.left == null) && 

                (node.right == null));

    }

  

    / * Рассчитать сумму всего листа

    Узлы на каждом уровне и возвращается

    умножение сумм * /

    int sumAndMultiplyLevelData()

    {

        return sumAndMultiplyLevelData(root);

    }

    int sumAndMultiplyLevelData(Node node)

    {

        // Дерево пусто

        if (node == null) {

            return 0;

        }

  

        int mul = 1; / * Для сохранения результата * /

  

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

        Queue<Node> q = new Queue<Node>();

  

        // ставим в очередь Root и инициализируем высоту

        q.Enqueue(node);

  

        // Выполнить обход уровня дерева

        while (true) {

  

            // NodeCount (размер очереди) указывает

            // количество узлов на текущем уровне.

            int NodeCount = q.Count;

  

            // Если в данный момент нет узлов

            // уровень, мы сделали

            if (NodeCount == 0) 

            {

                break;

            }

  

            // Инициализируем листовую сумму для текущего уровня

            int levelSum = 0;

  

            // Булева переменная, указывающая, найден ли лист

            // Узел на текущем уровне или нет

            bool leafFound = false;

  

            // Удаление всех узлов текущего уровня и

            // ставим в очередь все узлы следующего уровня

            while (NodeCount > 0) 

            {

                Node node1;

                node1 = q.Dequeue();

  

                / * если Node это лист, обновлять сумму на уровне * /

                if (isLeaf(node1))

                {

                    leafFound = true;

                    levelSum += node1.data;

                }

  

                // Добавляем дочерних узлов

                if (node1.left != null

                {

                    q.Enqueue(node1.left);

                }

                if (node1.right != null

                {

                    q.Enqueue(node1.right);

                }

                NodeCount--;

            }

  

            // Если мы нашли хотя бы один лист, мы умножаем

            // результат с суммой уровня.

            if (leafFound) 

            {

                mul *= levelSum;

            }

        }

  

        return mul; // Возвращаем результат

    }

  

    // Код драйвера

    public static void Main(String []args)

    {

  

        / * создание бинарного дерева и ввод

        узлы * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(2);

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

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

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

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

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

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

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

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

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

        Console.WriteLine("The final product value : "

                        + tree.sumAndMultiplyLevelData());

    }

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


Выход:

Final product value = 208

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

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

Найти умножение сумм данных листьев на тех же уровнях

0.00 (0%) 0 votes