פּרינט רעכט מיינונג פון אַ ביינערי בוים


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַקקאָליטע אַדאָובי אַמאַזאָן MakeMyTrip סנאַפּדעאַל
ביינערי טרי בוים בוים טראַווערסאַל

פּראָבלעם סטאַטעמענט

די פּראָבלעם "פּרינט רעכט מיינונג פון אַ ביינערי בוים" שטאַטן אַז איר באַקומען אַ ביינערי בוים. איצט איר דאַרפֿן צו געפֿינען די רעכט מיינונג פון דעם בוים. דאָ, רעכט מיינונג פון די ביינערי בוים מיטל צו דרוקן די סיקוואַנס ווי דער בוים קוקט ווען עס איז געקוקט פון די רעכט ריכטונג.

בייַשפּיל

פּרינט רעכט מיינונג פון אַ ביינערי בוים

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

דזשאַוואַ קאָד צו דרוקן די רעכט מיינונג פון אַ ביינערי בוים

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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N), מיר נאָר גיין דורך די נאָודז אין דעם בוים. אַזוי אויב עס זענען N נאָודז אין דעם בוים, די אַלגערידאַם ריקווייערז אָ (N) אַפּעריישאַנז צו דורכפירן.

ספעיס קאַמפּלעקסיטי

אָ (1). אויב פּלאַץ געניצט דורך קאַמפּיילער אָנלייגן איז נישט באַטראַכט, אַנדערש אוי) פּלאַץ איז פארלאנגט.