Рубрики

Вертикальная сумма в данном двоичном дереве | Комплект 1

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

Примеры:

      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

Нам нужно проверить горизонтальные расстояния от корня для всех узлов. Если два узла имеют одинаковое горизонтальное расстояние (HD), то они находятся на одной вертикальной линии. Идея HD проста. HD для корня равен 0, правый край (край, соединяющийся с правым поддеревом) рассматривается как +1 горизонтальное расстояние, а левый край — как -1 горизонтальное расстояние. Например, в приведенном выше дереве HD для узла 4 равен -2, HD для узла 2 равен -1, HD для 5 и 6 равен 0, а HD для узла 7 равен +2.
Мы можем выполнить упорядоченный обход данного двоичного дерева. Обходя дерево, мы можем рекурсивно вычислять HD. Мы изначально передаем горизонтальное расстояние как 0 для корня. Для левого поддерева мы передаем горизонтальное расстояние как горизонтальное расстояние корня минус 1. Для правого поддерева мы пропускаем горизонтальное расстояние как горизонтальное расстояние корня плюс 1.

Ниже приводится реализация Java для того же. HashMap используется для хранения вертикальных сумм для разных горизонтальных расстояний. Спасибо Nages за предложение этого метода.

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;

}

  
// Обходит дерево в порядке и
// заполняет hashMap, который содержит
// вертикальная сумма

void verticalSumUtil(Node *node, int hd,

                     map<int, int> &Map)

{

    // Базовый вариант

    if (node == NULL) return;

  

    // Повтор для левого поддерева

    verticalSumUtil(node->left, hd-1, Map);

  

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

    // отображаем запись соответствующего hd

    Map[hd] += node->data;

  

    // Повтор для правого поддерева

    verticalSumUtil(node->right, hd+1, Map);

}

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

void verticalSum(Node *root)

{

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

    // горизонтальное расстояние

    map < int, int> Map;

    map < int, int> :: iterator it;

  

    // заполняем карту

    verticalSumUtil(root, 0, Map);

  

    // Печатает значения, хранящиеся в VerticalSumUtil ()

    for (it = Map.begin(); it != Map.end(); ++it)

    {

        cout << it->first << ": "

             << it->second << endl;

    }

}

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

int main()

{

    // Создать двоичное дерево, как показано на рисунке выше

    Node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

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

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

  

    cout << "Following are the values of vertical"

            " sums with the positions of the "

            "columns with respect to root\n";

    verticalSum(root);

  

    return 0;

}
// Этот код предоставлен Адити Шарма

Джава

import java.util.HashMap;

   
// Класс для узла дерева

class TreeNode {

   

    // члены данных

    private int key;

    private TreeNode left;

    private TreeNode right;

   

    // Методы доступа

    public int key()        { return key; }

    public TreeNode left()  { return left; }

    public TreeNode right() { return right; }

   

    // Конструктор

    public TreeNode(int key)

   { this.key = key; left = null; right = null; }

   

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

    public void setLeft(TreeNode left)   { this.left = left; }

    public void setRight(TreeNode right) { this.right = right; }

}

   
// Класс для двоичного дерева

class Tree {

   

    private TreeNode root;

   

    // Конструкторы

    public Tree() { root = null; }

    public Tree(TreeNode n) { root = n; }

   

    // Метод, вызываемый классами потребителя

    // как основной класс

    public void VerticalSumMain() { VerticalSum(root); }

   

    // Оболочка над VerticalSumUtil ()

    private void VerticalSum(TreeNode root) {

   

        // базовый вариант

        if (root == null) { return; }

   

        // Создает пустой hashMap hM

        HashMap<Integer, Integer> hM =

                   new HashMap<Integer, Integer>();

   

        // Вызывает VerticalSumUtil () для сохранения

        // значения вертикальной суммы в чМ

        VerticalSumUtil(root, 0, hM);

   

        // Печатает значения, хранящиеся в VerticalSumUtil ()

        if (hM != null) {

            System.out.println(hM.entrySet());

        }

    }

   

    // Обходит дерево по порядку и строит

    // hashMap hM, который содержит вертикальную сумму

    private void VerticalSumUtil(TreeNode root, int hD,

                         HashMap<Integer, Integer> hM) {

   

        // базовый вариант

        if (root == null) {  return; }

   

        // Сохраняем значения в hM для левого поддерева

        VerticalSumUtil(root.left(), hD - 1, hM);

   

        // Обновляем вертикальную сумму для hD этого узла

        int prevSum = (hM.get(hD) == null) ? 0 : hM.get(hD);

        hM.put(hD, prevSum + root.key());

   

        // Сохраняем значения в hM для правого поддерева

        VerticalSumUtil(root.right(), hD + 1, hM);

    }

}

   
// Класс драйвера для тестирования методов verticalSum

public class Main {

   

    public static void main(String[] args) {

        / * Создать следующее двоичное дерево

              1

            / /

          2 3

         / / / /

        4 5 6 7

   

        * /

        TreeNode root = new TreeNode(1);

        root.setLeft(new TreeNode(2));

        root.setRight(new TreeNode(3));

        root.left().setLeft(new TreeNode(4));

        root.left().setRight(new TreeNode(5));

        root.right().setLeft(new TreeNode(6));

        root.right().setRight(new TreeNode(7));

        Tree t = new Tree(root);

   

        System.out.println("Following are the values of"

                           " vertical sums with the positions" +

                        " of the columns with respect to root ");

        t.VerticalSumMain();

    }

}

C #

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

using System;

using System.Collections.Generic;

  
// Класс для узла дерева

class TreeNode 

{

  

    // члены данных

    public int key;

    public TreeNode left;

    public TreeNode right;

  

    // Методы доступа

    public int Key()

    

        return key; 

    }

    public TreeNode Left() { return left; }

    public TreeNode Right() { return right; }

  

    // Конструктор

    public TreeNode(int key)

    

        this.key = key; 

        left = null;

        right = null

    }

  

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

    public void setLeft(TreeNode left) 

    

        this.left = left; 

    }

    public void setRight(TreeNode right) 

    

        this.right = right; 

    }

}

  
// Класс для двоичного дерева

class Tree 

{

    private TreeNode root;

  

    // Конструкторы

    public Tree() { root = null; }

    public Tree(TreeNode n) { root = n; }

  

    // Метод, вызываемый классами потребителя

    // как основной класс

    public void VerticalSumMain() 

    

        VerticalSum(root); 

    }

  

    // Оболочка над VerticalSumUtil ()

    private void VerticalSum(TreeNode root)

    {

  

        // базовый вариант

        if (root == null) { return; }

  

        // Создает пустой hashMap hM

        Dictionary<int

                   int> hM = new Dictionary<int

                                            int>();

  

        // Вызывает VerticalSumUtil () для сохранения

        // значения вертикальной суммы в чМ

        VerticalSumUtil(root, 0, hM);

  

        // Печатает значения, хранящиеся в VerticalSumUtil ()

        if (hM != null

        {

            Console.Write("[");

            foreach(KeyValuePair<int, int> entry in hM)

            {

                Console.Write(entry.Key + " = "

                              entry.Value + ", ");

            }

            Console.Write("]");

        }

    }

  

    // Обходит дерево по порядку и строит

    // hashMap hM, который содержит вертикальную сумму

    private void VerticalSumUtil(TreeNode root, int hD,

                                 Dictionary<int, int> hM)

    {

  

        // базовый вариант

        if (root == null) { return; }

  

        // Сохраняем значения в hM для левого поддерева

        VerticalSumUtil(root.Left(), hD - 1, hM);

  

        // Обновляем вертикальную сумму для hD этого узла

        int prevSum = 0;

        if(hM.ContainsKey(hD))

        {

            prevSum = hM[hD];

            hM[hD] = prevSum + root.Key();

        }

        else

            hM.Add(hD, prevSum + root.Key());

  

        // Сохраняем значения в hM для правого поддерева

        VerticalSumUtil(root.Right(), hD + 1, hM);

    }

}

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

public class GFG

{

    public static void Main(String[] args) 

    {

        / * Создать следующее двоичное дерево

            1

            / /

        2 3

        / / / /

        4 5 6 7

  

        * /

        TreeNode root = new TreeNode(1);

        root.setLeft(new TreeNode(2));

        root.setRight(new TreeNode(3));

        root.Left().setLeft(new TreeNode(4));

        root.Left().setRight(new TreeNode(5));

        root.Right().setLeft(new TreeNode(6));

        root.Right().setRight(new TreeNode(7));

        Tree t = new Tree(root);

  

        Console.WriteLine("Following are the values of"

                          " vertical sums with the positions" +

                          " of the columns with respect to root ");

        t.VerticalSumMain();

    }

}

  
// Этот код предоставлен Rajput-Ji

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

Сложность времени: O (n)

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

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

Вертикальная сумма в данном двоичном дереве | Комплект 1

0.00 (0%) 0 votes