이진 트리의 대각선 횡단

난이도 중급
자주 묻는 질문 아마존 팩트 셋 광신자 포카이트 신탁 알레그로 Quora
이진 트리 나무 트리 순회조회수 38

문제 정책

“이진 트리의 대각선 순회”문제는 이진 트리가 주어졌고 이제 주어진 트리에 대한 대각선 뷰를 찾아야 함을 나타냅니다. 오른쪽 상단에서 나무를 볼 때. 우리에게 보이는 노드는 이진 트리의 대각선보기입니다.

이진 트리의 대각선 횡단

2 7
3 4
5 6

설명

첫 번째 대각선에는 노드 2, 7이 있습니다. 그런 다음 두 번째 대각선은 3, 4를 가지며, 세 번째 대각선 5, 6과 유사합니다. 따라서 출력은 동일한 대각선의 요소가 동일한 라인에있는 방식으로 인쇄되었습니다.

접근

이진 트리의 대각선 횡단

문제는 우리에게 오른쪽 상단에서 볼 수있는 노드를 인쇄하도록 요청합니다. 그렇다면 문제를 어떻게 해결합니까?

이진 트리의 순회 순회를 수행합니다. 이렇게하는 동안 대각선 방향의 거리를 계속 추적합니다. 왼쪽 방향으로 이동할 때마다 대각선 거리에 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;
}

void diagonalView(node* root, int dis, map<int, vector<int>> &m){
    if(root){
        m[dis].push_back(root->data);
        // move in the left direction with dis+1 distance
        diagonalView(root->left, dis+1, m);
        // move in the right direction with dis distance
        diagonalView(root->right, dis, m);
    }
}

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, vector<int>> m;
    diagonalView(root, 0, m);
    for(auto x: m){
        for(auto nodes: x.second)
            cout<<nodes<<" ";
        cout<<endl;
    }
}
2 7
3 4
5 6

이진 트리의 대각선 순회를 인쇄하는 Java 코드

import java.util.*;

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

class Main{

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

  static void diagonalView(node root, int dis, Map<Integer, Vector<Integer>> m){
      if(root != null){
      	Vector<Integer> v = m.get(dis);
      	if(v == null){
      		v = new Vector<Integer>();
      		v.add(root.data);
      	}
      	else
      		v.add(root.data);
          m.put(dis, v);
          // move in the left direction with dis+1 distance
          diagonalView(root.left, dis+1, m);
          // move in the right direction with dis distance
          diagonalView(root.right, dis, m);
      }
  }

  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, Vector<Integer>> m = new TreeMap<Integer, Vector<Integer>>();
      diagonalView(root, 0, m);
      for(Map.Entry<Integer, Vector<Integer>> entry : m.entrySet())
          System.out.println(entry.getValue());
  }
}
[2, 7]
[3, 4]
[5, 6]

복잡성 분석

시간 복잡성

O (NlogN), 트리를 순회하고 값을 업데이트했기 때문입니다. 맵을 사용했기 때문에 삽입, 삭제, 검색은 O (logN) 시간에 이루어집니다.

공간 복잡성

의 위에), 지도에 모든 노드를 저장하고 있기 때문입니다. 공간 복잡성은 선형입니다.

Translate »