Намуди поёни дарахти дуӣ


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Акколити Amazon КупонДуния Flipkart Пардохт Озмоишгоҳҳои Walmart
Дарахти дуӣ Дарахт Траверсал дарахт

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

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

мисол

Намуди поёни дарахти дуӣ

5 6 4 7

усул

Равиш оддӣ аст, зеро мо аллакай мушкилеро, ки ба ин монанд аст, ҳал кардем. Масъала Намуди болоии дарахти дуӣ ба он монанд аст, ки мо бояд гиреҳҳоеро, ки аз самти боло ба мо намоёнанд, чоп кунем. Пас чӣ гуна мо мушкилро ҳал мекунем?

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

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

Рамзи C ++ барои чоп кардани Намуди поёни дарахти дуӣ

#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;
}

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,int> m;
    queue<pair<int,node*>> q;
    q.push(make_pair(0, root));
    m[0] = root->data;
    while(!q.empty()){
        pair<int, node*> now = q.front();
        q.pop();

        m[now.first] = now.second->data;
        if(now.second->left)
        q.push(make_pair(now.first - 1, now.second->left));
        if(now.second->right)
        q.push(make_pair(now.first + 1, now.second->right));
    }
    for(auto x: m)
        cout<<x.second<<" ";
}
5 6 4 7

Рамзи Java барои чоп кардани Намуди поёни дарахти дуӣ

import java.util.*;

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

class Main{

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

  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, Integer> m = new TreeMap<Integer, Integer>();
      Queue<node> q = new LinkedList<node>();
      q.add(root);
      m.put(root.hd, root.data);
      while(!q.isEmpty()){
          node now = q.remove();

          m.put(now.hd, now.data);
          if(now.left != null){
          	now.left.hd = now.hd - 1;
          	q.add(now.left);
          }
          if(now.right != null){
          	now.right.hd = now.hd + 1;
          	q.add(now.right);
          }
      }
      for(Map.Entry<Integer, Integer> entry : m.entrySet())
          System.out.print(entry.getValue()+" ");
  }
}
5 6 4 7

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

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

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

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

О (Н), дар сатҳи охирин метавонад (N + 1) / 2 бошад. Ҳамин тариқ, мураккабии фазо хаттӣ аст.