Вертикални збир у датом бинарном стаблу


Ниво тешкоће Средњи
Често питани у амазонка мицрософт
Бинарно дрво Дрво

Изјава о проблему

Проблем „Вертикална сума у ​​датом бинарном стаблу“ наводи да вам је дато бинарно стабло и да морамо пронаћи збир сваког вертикалног нивоа. Под вертикалним нивоом подразумевамо ако цртамо вертикалне линије на растојању од 1 јединице у левом и десном смеру, тада се каже да су чворови пресечени и-том линијом на и-ој вертикалној удаљености.

Пример

Улазни

Вертикални збир у датом бинарном стаблу

3, 5, 2, 5

objašnjenje: Чвор са вредношћу 3 је на нивоу -1, а чворови 1 и 4 су на нивоу 0. Тако је њихов збир 5. Слично томе, решавамо за чворове на нивоима 1 и 2. Тако је одговор 3, 5, 3, 5.

Вертикални збир у датом бинарном стаблу

Овде број испод линија означава хоризонтални ниво сваке линије.

Приступ вертикалном збиру у датом бинарном стаблу

Да бисмо решили овај проблем, сваком чвору ћемо доделити по један хоризонтални ниво и користићемо а Мапа да бисте сачували одговор за сваки хоризонтални ниво. Тако на крају имамо збир за сваки ниво, јер смо на крају прешли све чворове бинарно стабло.

Приступ хоризонталној удаљености је једноставан. Корену додељујемо 0, а ако се померимо десно од корена, додељујемо 1 и -1 за лево. Слично томе, за чвор на хоризонталном нивоу или хоризонталној удаљености „х“ додељујемо х-1 лево и х + 1 десно. Сада ћемо једноставно прећи стабло и наставити додавати вредност на сваком чвору на мапу где је кључ хоризонтална удаљеност.

код

Ц ++ код за вертикални збир у датом бинарном стаблу

#include<bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node *left;
    node *right;
};

node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
}


void fillVerticalSums(node *root,int horizontalLevel,map<int,int> &verticalSums){

    // base case
    if(!root)
        return;
    // recursively call for the left subtree
    fillVerticalSums(root->left, horizontalLevel-1, verticalSums);
    // add the value of current node to the current horizontal distance
    verticalSums[horizontalLevel] += root->data;
    // recursively call for right subtree
    fillVerticalSums(root->right, horizontalLevel+1, verticalSums);
}

void verticalSum(node *root)
{
    // map which stores the sum of nodes at each horizontal level
    map<int, int> verticalSums;
    fillVerticalSums(root, 0, verticalSums);
    // map stores the data in sorted order
    for(auto x: verticalSums)
        cout<<x.second<<" ";
}

int main()
{
    // here we have made a binary tree
    node *root = create(1);
    root->left = create(3);
    root->right = create(2);
    root->right->left = create(4);
    root->right->right = create(5);
    cout<<"The Vertical Sums: ";
    verticalSum(root);

    return 0;
}
The Vertical Sums: 3 5 2 5

Јава код за вертикални збир у датом бинарном стаблу

import java.util.*;
// Class that denotes a node of the tree
class Node 
{ 
    int data; 
    Node left, right; 
  
    public Node(int data) 
    { 
        this.data = data;
        left = right = null; 
    } 
}

class Tree 
{ 
    static Node root;
  static void fillVerticalSums(Node root, int horizontalLevel, TreeMap<Integer, Integer> verticalSums){
  
      // base case
      if(root == null)
          return;
      // recursively call for the left subtree
      fillVerticalSums(root.left, horizontalLevel-1, verticalSums);
      // add the value of current node to the current horizontal distance
      if(verticalSums.containsKey(horizontalLevel))
      	verticalSums.put(horizontalLevel, verticalSums.get(horizontalLevel) + root.data);
      else
      	verticalSums.put(horizontalLevel, root.data);
      // recursively call for right subtree
      fillVerticalSums(root.right, horizontalLevel+1, verticalSums);
  }

  static void verticalSum(Node root)
  {
      // map which stores the sum of nodes at each horizontal level
      TreeMap<Integer, Integer> verticalSums = new TreeMap<Integer, Integer>();
      fillVerticalSums(root, 0, verticalSums);
      // map stores the data in sorted order
      for(Map.Entry<Integer, Integer> entry: verticalSums.entrySet())
      	System.out.print(entry.getValue()+" ");
  }
  
    public static void main(String args[]) 
    { 
    	// here we have made a binary tree
        Tree tree = new Tree(); 
        tree.root = new Node(1); 
        tree.root.left = new Node(3); 
        tree.root.right = new Node(2); 
        tree.root.right.left = new Node(4); 
        tree.root.right.right = new Node(5); 
  
        System.out.print("The Vertical Sums: ");
        verticalSum(tree.root);
    }
}
The Vertical Sums: 3 5 2 5

Анализа сложености

Сложеност времена

О (Н лог Н)  јер смо управо прешли преко стабла које је прешло преко само Н чворова. А пошто уметање, претраживање и брисање траје евиденцију Н времена по операцији. Због тога имамо лог Н фактор.

Сложеност простора

НА) јер смо у дрвету сачували само Н чворова.