Рубрики

Произведение всех листовых узлов двоичного дерева

По заданному двоичному дереву найти произведение всех листовых узлов.

Примеры:

Input : 
        1
      /   \
     2     3
    / \   / \
   4   5 6   7
          \
           8
Output :
product = 4 * 5 * 8 * 7 = 1120

Идея состоит в том, чтобы обойти дерево любым способом и проверить, является ли узел листовым или нет. Если узел является конечным узлом, умножьте данные узла на переменную prod, используемую для хранения продуктов конечных узлов.

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

C ++

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

using namespace std;

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

struct Node {

    int data;

    Node *left, *right;

};

  
// вернуть новый узел

Node* newNode(int data)

{

    Node* temp = new Node();

    temp->data = data;

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

    return temp;

}

  
// функция полезности, которая вычисляет
// произведение всех листовых узлов

void leafProduct(Node* root, int& prod)

{

    if (!root)

        return;

  

    // корень данных продукта в prod if

    // корень - это листовой узел

    if (!root->left && !root->right)

        prod *= root->data;

  

    // распространяться рекурсивно слева

    // и правое поддерево

    leafProduct(root->left, prod);

    leafProduct(root->right, prod);

}

  
// Драйвер программы

int main()

{

  

    // построить двоичное дерево

    Node* root = newNode(1);

    root->left = newNode(2);

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

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

    root->right = newNode(3);

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

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

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

  

    // переменная для хранения продукта листовых узлов

    int prod = 1;

    leafProduct(root, prod);

    cout << prod << endl;

    return 0;

}

Джава

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

class GFG

{

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

static class Node 

    int data; 

    Node left, right; 

}; 

  
// вернуть новый узел

static Node newNode(int data) 

    Node temp = new Node(); 

    temp.data = data; 

    temp.left = temp.right = null

    return temp; 

  
// продукт

static int prod = 1;

  
// функция полезности, которая вычисляет
// произведение всех листовых узлов

static void leafProduct(Node root ) 

    if (root == null

        return

  

    // корень данных продукта в prod if

    // корень - это листовой узел

    if (root.left == null && root.right == null

        prod *= root.data; 

  

    // распространяться рекурсивно слева

    // и правое поддерево

    leafProduct(root.left); 

    leafProduct(root.right); 

  
// Драйвер программы

public static void main(String args[])

  

    // построить двоичное дерево

    Node root = newNode(1); 

    root.left = newNode(2); 

    root.left.left = newNode(4); 

    root.left.right = newNode(5); 

    root.right = newNode(3); 

    root.right.right = newNode(7); 

    root.right.left = newNode(6); 

    root.right.left.right = newNode(8); 

  

    // переменная для хранения продукта листовых узлов

    prod = 1

    leafProduct(root); 

    System.out.println(prod );

}

  
// Этот код предоставлен Арнабом Кунду

C #

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

using System;

  

class GFG

{

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

public class Node 

    public int data; 

    public Node left, right; 

}; 

  
// вернуть новый узел

static Node newNode(int data) 

    Node temp = new Node(); 

    temp.data = data; 

    temp.left = temp.right = null

    return temp; 

  
// продукт

static int prod = 1;

  
// функция полезности, которая вычисляет
// произведение всех листовых узлов

static void leafProduct(Node root ) 

    if (root == null

        return

  

    // корень данных продукта в prod if

    // корень - это листовой узел

    if (root.left == null && root.right == null

        prod *= root.data; 

  

    // распространяться рекурсивно слева

    // и правое поддерево

    leafProduct(root.left); 

    leafProduct(root.right); 

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

public static void Main(String []args)

  

    // построить двоичное дерево

    Node root = newNode(1); 

    root.left = newNode(2); 

    root.left.left = newNode(4); 

    root.left.right = newNode(5); 

    root.right = newNode(3); 

    root.right.right = newNode(7); 

    root.right.left = newNode(6); 

    root.right.left.right = newNode(8); 

  

    // переменная для хранения продукта листовых узлов

    prod = 1; 

    leafProduct(root); 

    Console.WriteLine(prod );

}
}

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

Выход:

1120

Сложность времени: O (n), где n — общее количество узлов в дереве.

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

Произведение всех листовых узлов двоичного дерева

0.00 (0%) 0 votes