Ուղղահայաց գումար տրված երկուական ծառի մեջ


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Microsoft
Երկուական ծառ ծառ

Խնդիրի հայտարարություն

«Ուղղահայաց գումար տրված երկուական ծառի մեջ» խնդիրը նշում է, որ ձեզ տրվում է երկուական ծառ, և մենք պետք է գտնենք յուրաքանչյուր ուղղահայաց մակարդակի հանրագումարը: Ուղղահայաց մակարդակ ասելով `նկատի ունենք, եթե ձախ և աջ ուղղությամբ 1 միավորի հեռավորության վրա ուղղահայաց գծեր ենք գծում, ապա ասում են, որ ith գծով հատված հանգույցները գտնվում են ուղղահայաց հեռավորության վրա:

Օրինակ

Մուտքային

Ուղղահայաց գումար տրված երկուական ծառի մեջ

3, 5, 2, 5

Բացատրությունը. 3 արժեք ունեցող հանգույցը գտնվում է -1 մակարդակում, իսկ 1 և 4 հանգույցները գտնվում են 0 մակարդակում: Այսպիսով, դրանց գումարը 5. Նմանապես, մենք լուծում ենք 1 և 2 մակարդակներում գտնվող հանգույցների համար: Այսպիսով, պատասխանը 3, 5, 3, 5 է:

Ուղղահայաց գումար տրված երկուական ծառի մեջ

Այստեղ գծերի տակ գտնվող թիվը նշանակում է յուրաքանչյուր տողի հորիզոնական մակարդակը:

Ուղղահայաց գումարի մոտեցումը տրված երկուական ծառի մեջ

Այս խնդրի լուծման համար յուրաքանչյուր հանգույցին մենք որոշ հորիզոնական մակարդակ ենք նշանակելու և օգտագործելու ենք a Քարտեզը յուրաքանչյուր հորիզոնական մակարդակի համար պատասխանը պահելու համար: Այսպիսով, ի վերջո, մենք յուրաքանչյուր մակարդակի համար ունենք գումար, որովհետև, ի վերջո, մենք անցել ենք երկուական ծառ.

Հորիզոնական հեռավորության վերաբերյալ մոտեցումը պարզ է: Արմատին նշանակում ենք 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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N տեղեկագիր N)  որովհետև մենք պարզապես անցանք ծառի վրայով, որը մենք անցնում ենք միայն N հանգույցների վրայով: Եվ քանի որ տեղադրումը, որոնումը և ջնջումը յուրաքանչյուր գործողության համար վերցնում են տեղեկամատյան N ժամանակ: Այդ պատճառով մենք ունենք տեղեկամատյան N գործոն:

Տիեզերական բարդություն

ՎՐԱ) քանի որ ծառի մեջ մենք պահել ենք միայն N հանգույց: