İkili ağacın sərhəd keçidi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Amazon Piyada çox yol qət eləmək Kritikal həlləri microsoft Morgan Stanley PayU Snapdeal
İkili ağac Ağac Ağacın keçidiBaxılıb 72

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

"İkili ağacın sərhəd keçməsi" problemi sizə ikili bir ağac verildiyini bildirir. İndi a sərhəd görünüşünü yazdırmalısınız ikili ağac. Burada sərhəd keçidi bütün qovşaqların ağacın sərhədi kimi göstərildiyi deməkdir. Düyünlər yuxarı, sol, alt və sağ tərəfdən saat yönünün əks istiqamətində görünür. Ancaq bu fikirlərin hamısını birbaşa çap edərdiksə, eyni qovşaqların dəfələrlə çapı ilə nəticələnəcəkdir. Beləliklə, sərhəd görünüşünü qovşaqların təkrarlanmaması üçün yazdırın.

misal

Pin

2 3 5 6 4 7

Izahat

Burada bütün qovşaqlar sərhəd qovşaqlarıdır. Ancaq qovşaqları saat yönünün əks istiqamətində yazdırmalıyıq. Beləliklə, 2-ci olan kökdən başlayırıq. Sonra eyni qaydada hərəkət edirik və 2, 3, 4, 6, 4, 7 qovşaqlarını çap edirik.

İkili ağacın sərhəd keçidiPin

5 7 9 1 4 3

Yanaşma

Problem ağacın sərhədini yazmağımızı xahiş edir, burada sol, sağ və alt sərhəd var. Ağacın sol və ya sağ sərhədi yoxdursa. kök özü sol və ya sağ sərhəd kimi qəbul edilir. Həm də bir şərt var ki, sərhəd qovşaqlarını yazdırırıqsa, iki qovşaqdan heç birinin dəfələrlə çap olunmamasına diqqət yetirməliyik.

Problemi həll etmək üçün ağacın sol sərhədindən başlayacağıq. Bir düyün sol tərəfdən görünürsə, bir düyünün sol sərhədə aid olduğunu deyirik. Eynilə, sağ düyünləri və yarpaq düyünlərini təyin edirik. Sol sərhədi yazdırmaq üçün ağacdan elə bir şəkildə keçəcəyik ki, kökün sol bir düyünü varsa, o zaman sağ düyününə keçin. Bir dəfə yarpaq düyününə çatacağıq. Yarpaq düyünlərini çap etmirik, çünki rekursiv olaraq ayrı-ayrılıqda yarpaq düyünlərini çap edirik. Sol sərhədlə bitdikdən sonra.

İlk növbədə sol subtree yarpaqları çap edərək rekursiv şəkildə yarpaq düyünlərini çap edirik. Sol alt ağac yarpaqlarını çap etdikdən sonra yarpaqları sağ alt ağacda çap edin. Bu şəkildə bütün yarpaq düyünləri saat yönünün əks istiqamətində yazdırılacaqdır. Yarpaqları yazdırdıqdan sonra sağ sərhədin qovşaqlarını çap edirik. Bu dəfə qovşaqların aşağıdan yuxarıya doğru yazdırılması lazımdır. Beləliklə içəridə rekursiya, əvvəlcə ağacın sol və ya sağ alt ağacını həll edirik və sonra cari düyünü pMicrrint edirik.

İkili ağacın Sərhəd keçidini çap etmək üçün C ++ kodu

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

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

// print the leaves (nodes from the bottom)
void printLeaves(node* root)
{
  if(root){
    // recursively solve the problem for the left subtree
    printLeaves(root->left);
    // if current node is a leaf
    if ((root->left) == NULL && (root->right) == NULL)
      cout<<root->data<<" ";
    // recursively solve the problem for right subtree
    printLeaves(root->right);
  }
}

// print all the nodes of left boundary
// this function will not print the leaves viewed from left side
void printLeft(node* root)
{
  if(root){
    if(root->left != NULL){
      cout<<root->data<<" ";
      // recursively move down the left subtree
      printLeft(root->left);
    }
    else if(root->right){
      cout<<root->data<<" ";
      // recursively move down the right subtree
      printLeft(root->right);
    }
  }
}

// print all the nodes of right boundary
// this function will not print the leaves viewed from the right side
void printRight(node* root)
{
  // printing is done after moving down the tree
  // thus printing is done in bottom up manner
  if(root){
    if (root->right) {
      printRight(root->right);
      cout<<root->data<<" ";
    }
    else if (root->left) {
      printRight(root->left);
      cout<<root->data<<" ";
    }
  }
}

void boundaryUtil(node* root)
{
  // first print the root, then print the left boundary
  // then the leaves which are seen from bottom
  // at last print the right boundary
  if(root){
    cout<<root->data<<" ";
    printLeft(root->left);
    printLeaves(root->left);
    printLeaves(root->right);
    printRight(root->right);
  }
}

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

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

  boundaryUtil(root);
}
5 7 9 1 4 3

İkili ağacın sərhəd keçidini yazdırmaq üçün Java kodu

import java.util.*;

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

class Main{

  // print the leaves (nodes from the bottom)
  static void printLeaves(node root)
  {
    if(root != null){
      // recursively solve the problem for the left subtree
      printLeaves(root.left);
      // if current node is a leaf
      if ((root.left) == null && (root.right) == null)
        System.out.print(root.data+" ");
      // recursively solve the problem for right subtree
      printLeaves(root.right);
    }
  }

  // print all the nodes of left boundary
  // this function will not print the leaves viewed from left side
  static void printLeft(node root)
  {
    if(root != null){
      if(root.left != null){
        System.out.print(root.data+" ");
        // recursively move down the left subtree
        printLeft(root.left);
      }
      else if(root.right != null){
        System.out.print(root.data+" ");
        // recursively move down the right subtree
        printLeft(root.right);
      }
    }
  }

  // print all the nodes of right boundary
  // this function will not print the leaves viewed from the right side
  static void printRight(node root)
  {
    // printing is done after moving down the tree
    // thus printing is done in bottom up manner
    if(root != null){
      if(root.right != null){
        printRight(root.right);
        System.out.print(root.data+" ");
      }
      else if(root.left != null){
        printRight(root.left);
        System.out.print(root.data+" ");
      }
    }
  }

  static void boundaryUtil(node root)
  {
    // first print the root, then print the left boundary
    // then the leaves which are seen from bottom
    // at last print the right boundary
    if(root != null){
      System.out.print(root.data+" ");
      printLeft(root.left);
      printLeaves(root.left);
      printLeaves(root.right);
      printRight(root.right);
    }
  }

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

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

    boundaryUtil(root);
  }
}
5 7 9 1 4 3

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki ağacın bütün düyünlərindən keçdik. PrintLeft, printRight və printLeaves funksiyasından istifadə edərkən qovşaqlardan keçirik. Beləliklə, zamanın mürəkkəbliyi doğrudur.

Kosmik Mürəkkəblik

O (H), burada H ağacın hündürlüyüdür. Bunun səbəbi kompilyator yığınının yer istifadə etməsidir. Və sərhəd elementlərini çap etmək üçün istifadə olunan funksiyalar kompilyator yığını üçün sayılan rekursiyadan istifadə edir.

Crack Sistemi Dizayn Müsahibələri
Translate »