Давраи диагоналии дарахти дуӣ


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon Factset Фараж Фуркайтҳо Oracle PayU Quora
Дарахти дуӣ Дарахт Траверсал дарахт

Изҳороти мушкилот

Масъалаи "Гузариши диагоналии дарахти дуӣ" мегӯяд, ки ба шумо дарахти дуӣ дода шудааст ва акнун ба шумо лозим аст, ки намуди диагоналиро барои дарахти додашуда пайдо кунед. Вақте ки мо дарахтро аз самти боло-рост мебинем. Гиреҳҳое, ки барои мо намоёнанд, намуди диагоналии дарахти дуӣ мебошанд.

мисол

Давраи диагоналии дарахти дуӣ

2 7
3 4
5 6

Шарҳ

Диагонали аввал дар он гиреҳҳои 2, 7 дорад. Пас диагонали дуюм 3, 4 дорад, ба ҳамин монанд барои диагонали сеюм 5, 6. Ҳамин тариқ, натиҷа тавре чоп шудааст, ки элементҳои ҳамон диагонал дар ҳамон сатр бошанд.

усул

Давраи диагоналии дарахти дуӣ

Мушкилот аз мо талаб мекунад, ки гиреҳҳоеро, ки барои мо аз самти боло-рост намоёнанд, чоп кунем. Пас чӣ гуна мо мушкилро ҳал мекунем?

Мо як гардиши ғайримуқаррарии дарахти дуӣ мекунем. Ҳангоми ин кор, мо масофаро дар самти диагоналӣ пайгирӣ хоҳем кард. Ҳар вақте ки мо ба самти чап ҳаракат мекунем, ба масофаи диагоналӣ 1 илова мекунем ва агар ба самти дуруст ҳаракат кунем, ба масофа ягон арзише илова намекунем. Ҳамин тавр, ҳангоми иҷрои ин амал мо гиреҳҳоеро, ки дар а ташриф оварда шудаанд, пайгирӣ хоҳем кард харита. Мо харитаеро бо масофаи диагоналӣ ҳамчун калид ва векторро ҳамчун арзиш созем. зеро мо гиреҳҳоро бо масофаи диагоналӣ дар вектор илова мекунем. Ва тавре ки мо тамоми чизро тай мекардем дарахт. Пас аз гузаштан, мо гиреҳҳоро дар векторҳо мувофиқи масофаи диагоналӣ нигоҳ медоштем.

Пас аз ҳамаи ин ҳисобҳо, танҳо элементҳоро дар харита чоп кунед, дар ҳоле ки гиреҳҳоро аз ҳар як вектор ҷудо кунед.

Рамзи C ++ барои чоп кардани Diagonal Traversal of Bree Binary

#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

Рамзи Java барои чоп кардани диагонали траверсали дарахти дуӣ

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]

Таҳлили мураккабӣ

Мураккабии вақт

О (NlogN), зеро мо дарахтро тай кардем ва арзишҳоро нав кардем. Азбаски мо харитаро истифода кардаем, дохилкунӣ, ҳазф ва ҷустуҷӯ дар вақти O (logN) анҷом дода мешавад.

Мураккабии фазо

O (N), зеро мо ҳамаи гиреҳҳоро дар харита нигоҳ медорем. Мураккабии фазо хаттӣ аст.