Өгөгдсөн хоёртын модны босоо нийлбэр


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Microsoft-
Хоёртын мод Мод

Асуудлын мэдэгдэл

“Өгөгдсөн хоёртын модны босоо нийлбэр” гэсэн бодлогод танд хоёртын мод өгөгдсөн бөгөөд бид босоо түвшин тус бүрийн нийлбэрийг олох хэрэгтэй. Босоо түвшинд бид босоо шугамыг зүүн ба баруун чиглэлд 1 нэгжийн зайд татвал ith шугамаар гаталсан зангилаа ith босоо зайд байна гэсэн үг юм.

Жишээ нь

Оролт

Өгөгдсөн хоёртын модны босоо нийлбэр

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 хүчин зүйлтэй болсон.

Сансрын нарийн төвөгтэй байдал

O (N) Учир нь бид модонд зөвхөн N зангилаа хадгалсан.