Рубрики

Вертикальная сумма в двоичном дереве | Комплект 2 (Оптимизировано пространство)

По заданному двоичному дереву найдите вертикальную сумму узлов, которые находятся на одной вертикальной линии. Выведите все суммы через разные вертикальные линии.

Примеры:

      1
    /   \
  2      3
 / \    / \
4   5  6   7

Дерево имеет 5 вертикальных линий

Vertical-Line-1 имеет только один узел 4 => вертикальная сумма равна 4
Vertical-Line-2: имеет только один узел 2 => вертикальная сумма равна 2
Vertical-Line-3: имеет три узла: 1,5,6 => вертикальная сумма 1 + 5 + 6 = 12
Vertical-Line-4: имеет только один узел 3 => вертикальная сумма равна 3
Vertical-Line-5: имеет только один узел 7 => вертикальная сумма равна 7

Таким образом, ожидаемый результат составляет 4, 2, 12, 3 и 7

Мы обсудили решение на основе хеширования в наборе 1 . Решение на основе хеширования требует поддержки хеш-таблицы. Мы знаем, что хеширование требует больше места, чем количество записей в нем. В этом посте обсуждается решение на основе двусвязного списка . Обсуждаемое здесь решение требует только n узлов связанного списка, где n — общее количество вертикальных линий в двоичном дереве. Ниже приведен алгоритм.

verticalSumDLL(root)
1)  Create a node of doubly linked list node 
    with value 0. Let the node be llnode.
2)  verticalSumDLL(root, llnode)

verticalSumDLL(tnode, llnode)
1) Add current node's data to its vertical line
        llnode.data = llnode.data + tnode.data;
2) Recursively process left subtree
   // If left child is not empty
   if (tnode.left != null)
   {
      if (llnode.prev == null)
      {
          llnode.prev = new LLNode(0);
          llnode.prev.next = llnode;
      }
      verticalSumDLLUtil(tnode.left, llnode.prev);
   }
3)  Recursively process right subtree
   if (tnode.right != null)
   {
      if (llnode.next == null)
      {
          llnode.next = new LLNode(0);
          llnode.next.prev = llnode;
      }
      verticalSumDLLUtil(tnode.right, llnode.next);
   }

C ++

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

  

using namespace std;

  
/// Структура дерева

struct TNode{

    int key;

    struct TNode *left, *right;

};

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

TNode* newTNode(int key)

{

    TNode* temp = new TNode;

    temp->key = key;

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

    return temp;

}

  
/// Структура двусвязного списка

struct LLNode{

    int key;

    struct LLNode *prev, *next;

};

  
/// Функция для создания нового узла связанного списка

LLNode* newLLNode(int key)

{

    LLNode* temp = new LLNode;

    temp->key = key;

    temp->prev = temp->next = NULL;

    return temp;

}

  
/// Функция, которая создает связанный список и хранит
/// вертикальная сумма в нем.

void verticalSumDLLUtil(TNode *root, LLNode *sumNode)

{

    /// Обновляем сумму текущей строки, добавляя значение

    /// текущего узла дерева.

    sumNode->key = sumNode->key + root->key;

  

    /// Рекурсивный вызов левого поддерева.

    if(root->left)

    {

        if(sumNode->prev == NULL)

        {

            sumNode->prev = newLLNode(0);

            sumNode->prev->next = sumNode;

        }

        verticalSumDLLUtil(root->left, sumNode->prev);

    }

  

    /// Рекурсивный вызов правого поддерева.

    if(root->right)

    {

        if(sumNode->next == NULL)

        {

            sumNode->next = newLLNode(0);

            sumNode->next->prev = sumNode;

        }

        verticalSumDLLUtil(root->right, sumNode->next);

    }

}

  
/// Функция для печати вертикальной суммы дерева.
/// Он использует verticalSumDLLUtil () для вычисления суммы.

void verticalSumDLL(TNode* root)

{

    /// Создать узел связанного списка для

    /// строка, проходящая через корень.

    LLNode* sumNode = newLLNode(0);

  

    /// Вычисляем вертикальную сумму разных линий.

    verticalSumDLLUtil(root, sumNode);

  

    /// Сделать указатель на двусвязный список

    /// к первому узлу в списке.

    while(sumNode->prev != NULL){

        sumNode = sumNode->prev;

    }

  

    /// Вывести вертикальную сумму разных строк

    /// двоичного дерева.

    while(sumNode != NULL){

        cout << sumNode->key <<" ";

        sumNode = sumNode->next;

    }

}

  

int main()

{

    / *

                 1

                / /

               / /

              2 3

             / / / /

            / / / /

           4 5 6 7

    * /

    TNode *root = newTNode(1);

    root->left = newTNode(2);

    root->right = newTNode(3);

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

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

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

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

  

    cout << "Vertical Sums are\n";

    verticalSumDLL(root);

    return 0;

}

  
// Этот код предоставлен <b> Рахулом Титэром </ b>

Джава

// Java-реализация космического оптимизированного решения
// найти вертикальную сумму.

  

public class VerticalSumBinaryTree

{

    // Печатает вертикальную сумму разных вертикалей

    // строки в дереве. Этот метод в основном использует

    // verticalSumDLLUtil ().

    static void verticalSumDLL(TNode root)

    {

        // Создаем двусвязный узел списка

        // сохранить сумму строк, проходящих через корень.

        // Вертикальная сумма инициализируется как 0.

        LLNode llnode = new LLNode(0);

  

        // Вычисляем вертикальную сумму разных линий

        verticalSumDLLUtil(root, llnode);

  

        // llnode относится к сумме вертикальной линии

        // проходим через корень. Переместитесь в

        // крайняя левая строка

        while (llnode.prev != null)

            llnode = llnode.prev;

  

        // Печатает вертикальную сумму всех строк, начинающихся

        // от крайней левой вертикальной линии

        while (llnode != null)

        {

            System.out.print(llnode.data +" ");

            llnode = llnode.next;

        }

    }

  

    // Создает связанный список

    static void verticalSumDLLUtil(TNode tnode,

                                   LLNode llnode)

    {

        // Добавить данные текущего узла к его вертикальной линии

        llnode.data = llnode.data + tnode.data;

  

        // Рекурсивно обрабатывать левое поддерево

        if (tnode.left != null)

        {

            if (llnode.prev == null)

            {

                llnode.prev = new LLNode(0);

                llnode.prev.next = llnode;

            }

            verticalSumDLLUtil(tnode.left, llnode.prev);

        }

  

        // Обработка правого поддерева

        if (tnode.right != null)

        {

            if (llnode.next == null)

            {

                llnode.next = new LLNode(0);

                llnode.next.prev = llnode;

            }

            verticalSumDLLUtil(tnode.right, llnode.next);

        }

    }

  

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

    public static void main(String[] args)

    {

        // Построим дерево, показанное выше

        TNode root = new TNode(1);

        root.left = new TNode(2);

        root.right = new TNode(3);

        root.left.left = new TNode(4);

        root.left.right = new TNode(5);

        root.right.left = new TNode(6);

        root.right.right = new TNode(7);

  

        System.out.println("Vertical Sums are");

        verticalSumDLL(root);

    }

  

    // Узел двусвязного списка

    static class LLNode

    {

        int data;

        LLNode prev, next;

        public LLNode(int d) { data = d; }

    }

  

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

    static class TNode

    {

        int data;

        TNode left, right;

        public TNode(int d) { data = d; }

    }

}

C #

// C # реализация пространства оптимизирована
// решение для поиска вертикальной суммы.

using System;

  

class GFG

{
// Печатает вертикальную сумму разных вертикалей
// строки в дереве. Этот метод в основном использует
// verticalSumDLLUtil ().

public static void verticalSumDLL(TNode root)

{

    // Создаем двусвязный узел списка

    // сохранить сумму строк, проходящих через корень.

    // Вертикальная сумма инициализируется как 0.

    LLNode llnode = new LLNode(0);

  

    // Вычисляем вертикальную сумму разных линий

    verticalSumDLLUtil(root, llnode);

  

    // llnode относится к сумме вертикальной линии

    // проходим через корень. Переместитесь в

    // крайняя левая строка

    while (llnode.prev != null)

    {

        llnode = llnode.prev;

    }

  

    // Печатает вертикальную сумму всех строк

    // начиная с крайней левой вертикальной линии

    while (llnode != null)

    {

        Console.Write(llnode.data + " ");

        llnode = llnode.next;

    }

}

  
// Создает связанный список

public static void verticalSumDLLUtil(TNode tnode, 

                                     LLNode llnode)

{

    // Добавить данные текущего узла в

    // его вертикальная линия

    llnode.data = llnode.data + tnode.data;

  

    // Рекурсивно обрабатывать левое поддерево

    if (tnode.left != null)

    {

        if (llnode.prev == null)

        {

            llnode.prev = new LLNode(0);

            llnode.prev.next = llnode;

        }

        verticalSumDLLUtil(tnode.left, llnode.prev);

    }

  

    // Обработка правого поддерева

    if (tnode.right != null)

    {

        if (llnode.next == null)

        {

            llnode.next = new LLNode(0);

            llnode.next.prev = llnode;

        }

        verticalSumDLLUtil(tnode.right, llnode.next);

    }

}

  
// Узел двусвязного списка

public class LLNode

{

    public int data;

    public LLNode prev, next;

    public LLNode(int d)

    {

        data = d;

    }

}

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

public class TNode

{

    public int data;

    public TNode left, right;

    public TNode(int d)

    {

        data = d;

    }

}

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

public static void Main(string[] args)

{

    // Построим дерево, показанное выше

    TNode root = new TNode(1);

    root.left = new TNode(2);

    root.right = new TNode(3);

    root.left.left = new TNode(4);

    root.left.right = new TNode(5);

    root.right.left = new TNode(6);

    root.right.right = new TNode(7);

  

    Console.WriteLine("Vertical Sums are");

    verticalSumDLL(root);

}
}

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


Выход :

Vertical Sums are
4 2 12 3 7 

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

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

Вертикальная сумма в двоичном дереве | Комплект 2 (Оптимизировано пространство)

0.00 (0%) 0 votes