مجموع عمودي في شجرة ثنائية معينة


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون Microsoft
شجرة ثنائية شجرة

المشكلة بيان

تنص مشكلة "المجموع الرأسي في شجرة ثنائية معينة" على أنه تم إعطاؤك شجرة ثنائية وعلينا إيجاد مجموع كل مستوى رأسي. نعني بالمستوى الرأسي أننا إذا رسمنا خطوطًا عمودية على مسافة وحدة واحدة في الاتجاهين الأيسر والأيمن ، فإن العقد التي يتقاطع معها الخط i يُقال إنها على مسافة رأسية.

مثال

إدخال

مجموع عمودي في شجرة ثنائية معينة

3, 5, 2, 5

التفسير: العقدة ذات القيمة 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 من العقد فقط في الشجرة.