Берилген экилик дарактын вертикалдык суммасы


Кыйынчылык деңгээли орто
Көп суралган Amazon Microsoft
Binary Tree дарак

Маселени билдирүү

"Берилген экилик дарактын вертикалдык суммасы" маселеси сизге экилик дарак берилгенин жана биз ар бир тик деңгээлдин суммасын табышыбыз керектигин билдирет. Вертикалдык деңгээл деп айтканда, эгерде биз вертикалдык сызыктарды сол жана оң багытта 1 бирдиктин аралыгында тартсак, анда ith сызыгы менен кесилген түйүндөр вертикалдык аралыкта дешет.

мисал

кирүү

Берилген экилик дарактын вертикалдык суммасы

3, 5, 2, 5

Explanation: 3 мааниси бар түйүн -1 деӊгээлинде, ал эми 1 жана 4 түйүндөрү 0 деӊгээлинде. Ошентип, алардын суммасы 5. Ошентип, биз 1 жана 2 денгээлдеги түйүндөрдү чечебиз. Ошентип, жооп 3, 5, 3, 5 болот.

Берилген экилик дарактын вертикалдык суммасы

Бул жерде саптардын астындагы сан ар бир саптын горизонталдык деңгээлин билдирет.

Берилген экилик дарактын вертикалдык суммасына ыкма

Бул маселени чечүү үчүн, биз ар бир түйүнгө горизонталдык деңгээлди бөлүп беребиз жана а карта ар бир горизонталдык деңгээл үчүн жоопту сактоо үчүн. Ошентип, акыр-аягы, бизде ар бир деңгээл үчүн сумма бар, анткени, акырында, биз бардык түйүндөрдү басып өттүк экилик дарак.

Горизонталдык аралыкка карата мамиле жөнөкөй. Тамырга 0, ал эми тамырдын оң жагына жылсак, солго 1 жана -1 белгилейбиз. Ошо сыяктуу эле, горизонталдык деңгээлдеги же “h” горизонталдык аралыкта жайгашкан түйүн үчүн биз h-1ди солго, h + 1ди оңго коёбуз. Эми, биз жөн гана бакты айланып өтүп, ар бир түйүндөгү маанини картага горизонталдык аралык болгон жерде кошо беребиз.

коду

Берилген экилик дарактын вертикалдык суммасы үчүн C ++ коду

#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

Берилген экилик дарактын вертикалдык суммасы үчүн Java коду

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

Комплекстик анализ

Убакыт татаалдыгы

O (N log N)  анткени биз жөн гана бактын үстүнөн өтүп, N түйүнүн гана басып өттүк. Киргизилгендиктен, издөө жана жок кылуу бир операцияга N убакытты алат. Ошондуктан бизде журналдын N фактору бар.

Космостун татаалдыгы

O (N) анткени биз бакта N түйүндөрдү гана сактадык.