جمع عمودی در یک درخت باینری داده شده


سطح دشواری متوسط
اغلب در آمازون مایکروسافت
درخت باینری درخت

بیان مسأله

مسئله "جمع عمودی در یک درخت باینری داده شده" بیان می کند که یک درخت باینری به شما داده می شود و ما باید جمع هر سطح عمودی را پیدا کنیم. منظور ما از سطح عمودی این است که اگر خطوط عمودی را در فاصله 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

کد جاوا برای جمع عمودی در یک درخت باینری داده شده

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 را می گیرد. به همین دلیل فاکتور log N داریم.

پیچیدگی فضا

بر) زیرا ما فقط N گره در درخت ذخیره کرده ایم.