Вид праворуч друку двійкового дерева


Рівень складності Легко
Часто запитують у Accolite саман Амазонка MakeMyTrip Snapdeal
Бінарне дерево Дерево Обхід дерева

Постановка проблеми

У проблемі «Право на друк бінарного дерева» вказано, що вам надано бінарне дерево. Тепер вам потрібно знайти правильний вигляд цього дерева. Тут правильний вигляд бінарного дерева означає друк послідовності, як це дерево виглядає, якщо дивитись з правильного напрямку.

Приклад

Вид праворуч друку двійкового дерева

2 7 4 6

Пояснення

Якщо ви спостерігаєте бінарне дерево у правильному напрямку. Ми можемо бачити лише ті вузли, які надруковані у вихідних даних. Оскільки вузли 3 і 5 ховаються за 7 і 4 відповідно.

Підхід до друку праворуч виду двійкового дерева

У цій проблемі нам потрібно знайти правильний погляд на двійкове дерево. Проблему можна вирішити за допомогою двох підходів. Один з них використовує чергу, а інший - рекурсію. Спочатку ми обговоримо підхід з використанням черги. Отже, для вирішення проблеми за допомогою чергу. Починаємо з кореня бінарного дерева. Для кожного рівня дерева ми продовжуємо зберігати вузли в черзі. Для зберігання вузлів наступного рівня нам доведеться здійснити обхід вузлів поточного рівня. Отже, коли ми подорожуємо по вузлах поточного рівня. Ми друкуємо останній вузол на цьому рівні. Коли ми спостерігаємо дерево з правого боку. Єдиний вузол, який нам видно, - це самий правий вузол на рівні. Цей підхід використовує чергу, яка займає місце.

Обговоримо рішення, використовуючи рекурсію. Рішення дуже схоже на рішення пошуку лівого виду дерева. При такому підході. Ми просто робимо обхід дерева, який протилежний такому, як внутрішній обхід. Але ми також відстежуємо рівень, на якому ми зараз перебуваємо, і максимальний рівень, досягнутий дотепер. Коли ми переходимо до правого піддерева перед лівим піддеревом. Кожного разу, коли ми виходимо на новий рівень у дереві. Спочатку ми стикаємось з самим правим вузлом. Тому ми завжди перевіряємо, чи поточний рівень більше максимального рівня, ми друкуємо вузол. Підхід кращий, якщо ми не враховуємо простір, необхідний для стека компілятора. Складність простору для проблеми залежить від висоти дерева, якщо врахувати простір, зайнятий стеком компілятора.

код

Код 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;
}

void printRightView(node* root, int level, int &max_level){
    if(root){
        if(level > max_level){
            max_level = level;
            cout << root->data <<" ";
        }
        printRightView(root->right, level+1, max_level);
        printRightView(root->left, level+1, max_level);
    }
}

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);

  int max_level = 0;
  printRightView(root, 1, max_level);
}
2 7 4 6

Код Java для друку правого подання двійкового дерева

import java.util.*;

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

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

  static int max_level;
  static void printRightView(node root, int level){
      if(root != null){
          if(level > max_level){
              max_level = level;
              System.out.print(root.data+" ");
          }
          printRightView(root.right, level+1);
          printRightView(root.left, level+1);
      }
  }

  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);
    
    max_level = 0;
    printRightView(root, 1);
  }
}
2 7 4 6

Аналіз складності

Складність часу

O (N), ми просто подорожуємо по вузлах у дереві. Отже, якщо у дереві є N вузлів, алгоритм вимагає виконання O (N) операцій.

Складність простору

O (1). Якщо простір, використаний стеком компілятора, не враховується, інакше O (H) потрібен простір.