په ورکړل شوي بائنری ونې کې عمودي جمع


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon د Microsoft
دوهم ونې ونې

ستونزه بیان

"په ورکړل شوې بائنري ونې کې عمودي مجموعه" ستونزه په ګوته کوي چې تاسو ته بائنری ونې درکول شوي او موږ اړتیا لرو د هرې عمودي کچې مجموعه ومومئ. د عمودي کچې په واسطه ، موږ پدې معنی یو چې که موږ په کی unit او ښیې خوا کې د 1 واحد په فاصله کې عمودی کرښې رسم کړو نو بیا نوډونه چې د ith لاین څخه تیریږي په ith عمودي واټن کې ویل کیږي.

بېلګه

ننوتۍ

په ورکړل شوي بائنری ونې کې عمودي جمع

3, 5, 2, 5

وضاحت: نوډ د 3 ارزښت سره سطح کې -1 کې دی ، او نوډونه 1 او 4 په سطح کې دي 0 پدې توګه د دوی مجموعه 5. ورته ده ، موږ د 1 او 2 کچې نوډونو لپاره حل کوو. پدې توګه ځواب 3 ، 5 ، 3 ، 5 دی.

په ورکړل شوي بائنری ونې کې عمودي جمع

دلته د لینونو لاندې شمیره د هرې کرښې افقی کچه په ګوته کوي.

په ورکړل شوي بائنري ونې کې د عمودي مجموعې لپاره لاره

د دې ستونزې حل کولو لپاره ، موږ به هرډول ته یو څه افقی کچه کړو او موږ به وکاروو نقشه د هرې افقي کچې لپاره ځواب ذخیره کول. په دې توګه ، په پای کې ، موږ د هرې کچې لپاره پیسې لرو ځکه چې په پای کې موږ د ټولو قضیو تثبیت کړې دوه لمبر ونه.

د افقي فاصلو په اړه چلند خورا اسانه دی. موږ 0 ته ریښې ته دنده ورکوو ، او که موږ د ریښې ښیې خوا ته لاړ شو ، نو موږ د کی for لپاره 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

په ورکړل شوي بائنري ونې کې د عمودي جمع لپاره جاوا کوډ

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 وخت نیسي. له همدې امله موږ د نګ فاکتور لرو.

د ځای پیچلتیا

O (N) ځکه چې موږ په ونه کې یوازې N نوډونه ساتلي دي.