주어진 이진 트리의 수직 합

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

문제 정책

"주어진 이진 트리의 수직 합계"문제는 이진 트리가 주어졌고 각 수직 수준의 합계를 찾아야한다고 말합니다. 수직 레벨이란 왼쪽과 오른쪽 방향으로 1 단위의 거리에 수직선을 그리면 i 번째 선이 교차하는 노드는 i 번째 수직 거리에 있다고합니다.

예

입력

핀

3, 5, 2, 5

설명 : 값이 3 인 노드는 수준 -1에 있고 노드 1과 4는 수준 0에 있습니다. 따라서 그 합계는 5입니다. 마찬가지로 수준 1과 2의 노드에 대해 해결하므로 답은 3, 5, 3, 5입니다.

핀

여기에서 선 아래의 숫자는 각 선의 수평 수준을 나타냅니다.

주어진 이진 트리에서 수직 합계에 대한 접근 방식

이 문제를 해결하기 위해 각 노드에 수평 수준을 할당하고 지도 각 수평 수준에 대한 답을 저장합니다. 따라서 결국 우리는 각 레벨에 대한 합계를 얻습니다. 왜냐하면 결국에는 모든 노드를 순회했기 때문입니다. 이진 트리.

수평 거리에 대한 접근 방식은 간단합니다. 루트에 0을 할당하고 루트의 오른쪽으로 이동하면 왼쪽에 1과 -1을 할당합니다. 마찬가지로 수평 수준 또는 수평 거리 "h"에있는 노드에 대해 h-1을 왼쪽에 할당하고 h + 1을 오른쪽에 할당합니다. 이제 우리는 단순히 트리를 횡단하고 키가 수평 거리 인 맵에 각 노드의 값을 계속 추가합니다.

암호

주어진 이진 트리의 수직 합계에 대한 C ++ 코드

#include<bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node *left;
    node *right;
};

node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
}


void fillVerticalSums(node *root,int horizontalLevel,map<int,int> &verticalSums){

    // base case
    if(!root)
        return;
    // recursively call for the left subtree
    fillVerticalSums(root->left, horizontalLevel-1, verticalSums);
    // add the value of current node to the current horizontal distance
    verticalSums[horizontalLevel] += root->data;
    // recursively call for right subtree
    fillVerticalSums(root->right, horizontalLevel+1, verticalSums);
}

void verticalSum(node *root)
{
    // map which stores the sum of nodes at each horizontal level
    map<int, int> verticalSums;
    fillVerticalSums(root, 0, verticalSums);
    // map stores the data in sorted order
    for(auto x: verticalSums)
        cout<<x.second<<" ";
}

int main()
{
    // here we have made a binary tree
    node *root = create(1);
    root->left = create(3);
    root->right = create(2);
    root->right->left = create(4);
    root->right->right = create(5);
    cout<<"The Vertical Sums: ";
    verticalSum(root);

    return 0;
}

The Vertical Sums: 3 5 2 5

주어진 이진 트리의 수직 합계에 대한 Java 코드

import java.util.*;
// Class that denotes a node of the tree
class Node 
{ 
    int data; 
    Node left, right; 
  
    public Node(int data) 
    { 
        this.data = data;
        left = right = null; 
    } 
}

class Tree 
{ 
    static Node root;
  static void fillVerticalSums(Node root, int horizontalLevel, TreeMap<Integer, Integer> verticalSums){
  
      // base case
      if(root == null)
          return;
      // recursively call for the left subtree
      fillVerticalSums(root.left, horizontalLevel-1, verticalSums);
      // add the value of current node to the current horizontal distance
      if(verticalSums.containsKey(horizontalLevel))
      	verticalSums.put(horizontalLevel, verticalSums.get(horizontalLevel) + root.data);
      else
      	verticalSums.put(horizontalLevel, root.data);
      // recursively call for right subtree
      fillVerticalSums(root.right, horizontalLevel+1, verticalSums);
  }

  static void verticalSum(Node root)
  {
      // map which stores the sum of nodes at each horizontal level
      TreeMap<Integer, Integer> verticalSums = new TreeMap<Integer, Integer>();
      fillVerticalSums(root, 0, verticalSums);
      // map stores the data in sorted order
      for(Map.Entry<Integer, Integer> entry: verticalSums.entrySet())
      	System.out.print(entry.getValue()+" ");
  }
  
    public static void main(String args[]) 
    { 
    	// here we have made a binary tree
        Tree tree = new Tree(); 
        tree.root = new Node(1); 
        tree.root.left = new Node(3); 
        tree.root.right = new Node(2); 
        tree.root.right.left = new Node(4); 
        tree.root.right.right = new Node(5); 
  
        System.out.print("The Vertical Sums: ");
        verticalSum(tree.root);
    }
}

The Vertical Sums: 3 5 2 5

복잡성 분석

시간 복잡성

O (N log N)  왜냐하면 우리는 단지 N 개의 노드를 횡단하는 트리를 횡단했기 때문입니다. 그리고 삽입 이후 검색 및 삭제는 작업 당 log N 시간이 걸립니다. 이것이 우리가 log N 인자를 갖는 이유입니다.

공간 복잡성

의 위에) 트리에 N 개의 노드 만 저장했기 때문입니다.