이진 트리의 오른쪽보기 인쇄


난이도 쉽게
자주 묻는 질문 Accolite 어도비 벽돌 아마존 MakeMyTrip 스냅 딜
이진 트리 나무 트리 순회

문제 정책

"이진 트리의 오른쪽보기 인쇄"문제는 이진 트리가 제공되었음을 나타냅니다. 이제이 트리의 올바른보기를 찾아야합니다. 여기서 이진 트리의 오른쪽보기는 올바른 방향에서 보았을 때 트리가 보이는대로 시퀀스를 인쇄하는 것을 의미합니다.

이진 트리의 오른쪽보기 인쇄

2 7 4 6

설명

이진 트리를 올바른 방향으로 관찰하면. 출력에 인쇄 된 노드 만 볼 수 있습니다. 노드 3과 5가 각각 7과 4 뒤에 숨겨지기 때문입니다.

이진 트리의 오른쪽보기를 인쇄하는 방법

이 문제에서 우리는 올바른보기를 찾아야합니다. 이진 트리. 이 문제는 두 가지 방법으로 해결할 수 있습니다. 그중 하나는 큐를 사용하고 다른 하나는 재귀를 사용합니다. 먼저 대기열을 사용하는 접근 방식에 대해 설명합니다. 따라서 문제를 해결하려면 변발. 이진 트리의 루트에서 시작합니다. 트리의 각 수준에 대해 대기열에 노드를 계속 저장합니다. 다음 레벨의 노드를 저장하려면 현재 레벨의 노드를 탐색해야합니다. 따라서 현재 수준의 노드를 탐색 할 때. 이 수준에서 마지막 노드를 인쇄합니다. 오른쪽에서 나무를 관찰 할 때. 우리에게 보이는 유일한 노드는 레벨에서 가장 오른쪽 노드입니다. 이 접근 방식은 공간을 차지하는 대기열을 사용합니다.

재귀를 사용하는 솔루션에 대해 논의 해 봅시다. 해결책은 나무의 왼쪽보기를 찾는 것과 매우 유사합니다. 이 접근법에서. 우리는 단순히 inorder traversal과 반대되는 트리의 순회를 수행합니다. 그러나 우리는 또한 우리가 현재있는 수준과 지금까지 도달 한 최대 수준을 추적합니다. 왼쪽 하위 트리 앞의 오른쪽 하위 트리로 이동합니다. 우리가 트리의 새로운 레벨에 들어갈 때마다. 먼저 가장 오른쪽 노드를 만납니다. 따라서 현재 레벨이 최대 레벨보다 큰지 항상 확인하고 노드를 인쇄합니다. 컴파일러 스택에 필요한 공간을 고려하지 않으면 접근 방식이 더 좋습니다. 컴파일러 스택이 차지하는 공간을 고려하면 문제의 공간 복잡성은 트리의 높이에 따라 달라집니다.

암호

이진 트리의 오른쪽보기를 인쇄하는 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

복잡성 분석

시간 복잡성

의 위에), 우리는 단지 트리의 노드를 순회하고 있습니다. 따라서 트리에 N 개의 노드가있는 경우 알고리즘은 O (N) 연산을 수행해야합니다.

공간 복잡성

O (1). 컴파일러 스택에서 사용하는 공간이 고려되지 않으면 오) 공간이 필요합니다.