이진 트리를 세로 순서로 인쇄

난이도 중급
자주 묻는 질문 수행자 아마존 BrowserStack 작은 골짜기 Flipkart 그루퍼 MakeMyTrip 네트 스코프 월마트 연구소
해시 나무 트리 순회조회수 78

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

이 문제에서 우리는 이진 트리 그리고 당신의 임무는 수직 순서로 이진 트리를 인쇄하는 것입니다.

입력

           1
        /    \ 
      2         3
    / \      /  \
  4    5    6    7
               \     \ 
                8      9

산출

4
2
+1 5 6 XNUMX
3 8
7
9

설명

이진 트리를 세로 순서로 인쇄

이진 트리를 수직 순서로 인쇄하는 알고리즘

  1. 다른 노드에 요소를 삽입하십시오.
  2. 거리를 0으로 설정합니다.
  3. true이면 루트가 null인지 확인한 다음 반환합니다.
  4. keyValue를지도의 키로 거리 값으로 설정합니다.
    1. 확인 "핵심 가치" null과 같습니다.
      1. 참이면 초기화 "핵심 가치" 새 벡터에 루트 값 (요소)을 추가합니다.
    2. 그렇지 않으면 이미 존재하기 때문에 해당 벡터에 루트 값을 추가하십시오.
  5. 거리를 넣고 "핵심 가치" 지도에서.
  6. 다음을 사용하여 printVerticalTree 함수를 재귀 적으로 호출합니다. "root.left", 거리 -1, "엠""root.right", 거리 +1, "엠" 왼쪽 및 오른쪽 하위 트리에 대해 각각.
  7. 지도 인쇄.

이진 트리를 세로로 인쇄하는 방법에 대한 설명

이진 트리를 수직 순서로 인쇄하는 주요 아이디어는 매번 인수로 전달되는 업데이트 된 값을 사용하여 함수를 재귀 적으로 호출하고 원하는 출력에 따라지도를 계속 업데이트하는 것입니다.

root, root.right, root.left, root.left.left 등에 노드 삽입으로 시작하여 값을 입력으로 사용합니다. 트리의 가장 왼쪽 요소부터 시작하여 이러한 입력을 하나씩 가져와야합니다. 벡터를 초기화 한 다음 벡터의 각 인덱스에 대한 키로 정수를 사용하여지도에 삽입합니다. 벡터에서 모든 값을 수직으로 저장 한 다음 거리와 keyValue를 맵에 "핵심 가치" 한 쌍이다.

주요 부분

루트를 처음 전달할 때는 null 값이 없습니다. 그런 다음 map.get (distance)는 keyValue에 저장합니다. 만약 keyValue가 null이면 값이없는 맵의 키로 'distance'를 의미하고 벡터 keyValue를 초기화하고 루트를 추가합니다. key는 root.key가 나타내는 요소를 의미합니다. keyValue가 null이 아니면 'key'와 함께 저장된 기존 값이 이미 있음을 의미합니다. "root.key"(표시되는 요소) 만 추가하면됩니다.

이 모든 것에서 거리라는 또 하나의 중요한 용어가 있습니다. 거리는 루트 노드에서 트리에있는 노드의 수직 거리를 의미합니다. 거리로 숫자를 얻습니다. 왼쪽 하위 트리로 음수를 얻고 오른쪽 하위 트리의 경우 양수를 얻고 루트 노드의 오른쪽 및 노드 아래에 루트에서 0 거리에있는 것으로 간주되며 인수로 재귀 적으로 전달합니다. 우리가 거리를 인자로 전달할 때마다, 이것은지도에서 키로 판명 된 몇 가지 값을 함께 저장할 것임을 의미합니다. 예를 들면 -2, -1, 0, 1, 2, 3. 이것은 우리가 요소를 저장할 각 벡터에 대한 키입니다.

지도에서 값을 인쇄해야합니다.지도의 모든 값에는 가장 왼쪽 요소부터 시작하여 가장 오른쪽 요소를 의미하는 -2에서 3까지의 키 (정렬 됨)가 있습니다. 모든 요소를 ​​수직으로 가져 와서 인쇄합니다.

이진 트리를 수직 순서로 인쇄하기위한 구현

C ++ 프로그램

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Node
{
    int key;
    Node *left, *right;
};
struct Node* newNode(int key)
{
    struct Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}
void printVerticalTree(Node* root, int distance, map<int, vector<int>> &mymap)
{
    if (root == NULL)
        return;

    mymap[distance].push_back(root->key);

    printVerticalTree(root->left, distance-1, mymap);

    printVerticalTree(root->right, distance+1, mymap);
}
void printVerticalOrder(Node* root)
{
    map < int,vector<int> > mymap;
    int distance = 0;
    printVerticalTree(root, distance,mymap);
    map< int,vector<int> > :: iterator it;
    for (it=mymap.begin(); it!=mymap.end(); it++)
    {
        for (int i=0; i<it->second.size(); ++i)
            cout << it->second[i] << " ";
        cout << endl;
    }
}
int main()
{
    Node *root = newNode(3);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(8);
    root->left->right = newNode(11);
    root->right->left = newNode(14);
    root->right->right = newNode(17);
    root->right->left->right = newNode(18);
    root->right->right->right = newNode(25);
    cout << "Vertical order traversal is \n";
    printVerticalOrder(root);
    return 0;
}
Vertical order traversal is
8
4
3 11 14
6 18
17
25

자바 프로그램

import java.util.TreeMap;
import java.util.Vector;
import java.util.Map.Entry;

class printBinarytreeVertical
{
    static class Node
    {
        int key;
        Node left;
        Node right;
        Node(int data)
        {
            key = data;
            left = null;
            right = null;
        }
    }
    static void printVerticalTree(Node root, int distance, TreeMap<Integer,Vector<Integer>> map)
    {

        if(root == null)
        {
            return;
        }
        Vector<Integer> keyValue = map.get(distance);
        if(keyValue == null)
        {
            keyValue = new Vector<>();
            keyValue.add(root.key);
        }
        else
            keyValue.add(root.key);

        map.put(distance, keyValue);

        printVerticalTree(root.left, distance-1, map);

        printVerticalTree(root.right, distance+1, map);
    }
    static void printVerticalOrder(Node root)
    {
        TreeMap<Integer,Vector<Integer>> m = new TreeMap<>();
        int distance =0;
        printVerticalTree(root,distance,m);
        for (Entry<Integer, Vector<Integer>> getentry : m.entrySet())
        {
            System.out.println(getentry.getValue());
        }
    }
    public static void main(String[] args)
    {
        Node root = new Node(3);
        root.left = new Node(4);
        root.right = new Node(6);
        root.left.left = new Node(8);
        root.left.right = new Node(11);
        root.right.left = new Node(14);
        root.right.right = new Node(17);
        root.right.left.right = new Node(18);
        root.right.right.right = new Node(25);
        System.out.println("Vertical Order traversal is");
        printVerticalOrder(root);
    }
}
Vertical Order traversal is
[8]
[4]
[3, 11, 14]
[6, 18]
[17]
[25]

이진 트리를 수직 순서로 인쇄하기위한 복잡성 분석

시간 복잡성

O (n 로그인) 어디에 "엔" 트리의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔" 트리의 요소 수입니다.

참조

균열 시스템 설계 인터뷰
Translate »