İkili ağacın diaqonal keçməsi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Məlumat dəsti Fanatics Fourkites Kahin PayU Quora
İkili ağac Ağac Ağacın keçidiBaxılıb 27

Problem bəyanat

“İkili ağacın diaqonal keçməsi” problemi sizə ikili ağac verildiyini və indi verilmiş ağac üçün diaqonal görünüşü tapmağın lazım olduğunu bildirir. Yuxarı sağ tərəfdən bir ağac gördükdə. Bizə görünən qovşaqlar ikili ağacın çarpaz görünüşüdür.

misal

İkili ağacın diaqonal keçməsiPin

2 7
3 4
5 6

Izahat

İlk çarpazda 2, 7 qovşaq var. Sonra ikinci diaqonal 3, 4-ə bərabərdir, üçüncü diaqonal 5, 6-ya bənzər. Beləliklə, çıxış eyni diaqonaldan olan elementlərin eyni sətirdə olacağı şəkildə çap olundu.

Yanaşma

İkili ağacın diaqonal keçməsiPin

Problem, yuxarıdan yuxarı istiqamətdən bizə görünən qovşaqları yazdırmağımızı xahiş edir. Bəs problemi necə həll edirik?

İkili ağacın qeyri-müəyyən bir keçidini edəcəyik. Bunu edərkən, diaqonal istiqamətdə məsafəni izləyəcəyik. Hər dəfə sol istiqamətdə hərəkət etdikdə diaqonal məsafəyə 1 əlavə edirik və düzgün istiqamətdə hərəkət etsək məsafəyə heç bir dəyər əlavə etmirik. Beləliklə, bunu edərkən a-da ziyarət olunan qovşaqları izləyəcəyik xəritə. Diaqonal məsafəni açar, dəyəri isə vektor olan bir xəritə yaradacağıq. çünki bir vektorda diaqonal məsafəli qovşaqları əlavə edəcəyik. Və bütün bunlardan keçdiyimiz kimi ağac. Keçiddən sonra vektorlardakı qovşaqları diaqonal məsafələrə görə saxlayardıq.

Bütün bu hesablamalardan sonra qovşaqları vektorların hər birindən ayırarkən elementləri xəritədə yazdırmaq kifayətdir.

İkili Ağacın Çapraz Çəkilməsini çap etmək üçün C ++ kodu

#include <bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node *left, *right;
};

node* create(int data){
    node* tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

void diagonalView(node* root, int dis, map<int, vector<int>> &m){
    if(root){
        m[dis].push_back(root->data);
        // move in the left direction with dis+1 distance
        diagonalView(root->left, dis+1, m);
        // move in the right direction with dis distance
        diagonalView(root->right, dis, m);
    }
}

int main(){
    node *root = create(2);
    root->left = create(3);
    root->right = create(7);
    root->left->left = create(5);
    root->left->right = create(4);
    root->left->right->left = create(6);

    map<int, vector<int>> m;
    diagonalView(root, 0, m);
    for(auto x: m){
        for(auto nodes: x.second)
            cout<<nodes<<" ";
        cout<<endl;
    }
}
2 7
3 4
5 6

Binary Tree Diagonal Traversal yazdırmaq üçün Java kodu

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
      node tmp = new node();
      tmp.data = data;
      tmp.left = tmp.right = null;
      return tmp;
  }

  static void diagonalView(node root, int dis, Map<Integer, Vector<Integer>> m){
      if(root != null){
      	Vector<Integer> v = m.get(dis);
      	if(v == null){
      		v = new Vector<Integer>();
      		v.add(root.data);
      	}
      	else
      		v.add(root.data);
          m.put(dis, v);
          // move in the left direction with dis+1 distance
          diagonalView(root.left, dis+1, m);
          // move in the right direction with dis distance
          diagonalView(root.right, dis, m);
      }
  }

  public static void main(String[] args){
    node root = create(2);
      root.left = create(3);
      root.right = create(7);
      root.left.left = create(5);
      root.left.right = create(4);
      root.left.right.left = create(6);

      Map<Integer, Vector<Integer>> m = new TreeMap<Integer, Vector<Integer>>();
      diagonalView(root, 0, m);
      for(Map.Entry<Integer, Vector<Integer>> entry : m.entrySet())
          System.out.println(entry.getValue());
  }
}
[2, 7]
[3, 4]
[5, 6]

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (NlogN), çünki ağacdan keçdik və dəyərləri yenilədik. Bir xəritə istifadə etdiyimiz üçün daxiletmə, silmə və axtarış O (logN) vaxtında aparılır.

Kosmik Mürəkkəblik

O (N), çünki bütün qovşaqları xəritədə saxlayırıq. Məkan mürəkkəbliyi doğrudur.

Translate »