มุมมองด้านล่างของทรีไบนารี


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคโคไลท์ อเมซอน คูปอง Flipkart Paytm Walmart Labs
ต้นไม้ไบนารี ต้นไม้ ทรีทราเวอร์ซัล

คำชี้แจงปัญหา

ปัญหา“ มุมมองด้านล่างของต้นไม้ไบนารี” ระบุว่าคุณได้รับต้นไม้ไบนารีและตอนนี้คุณต้องหามุมมองด้านล่างสำหรับสิ่งที่ระบุ ต้นไม้. เมื่อเราเห็นต้นไม้จากทางลง โหนดที่เรามองเห็นได้คือมุมมองด้านล่างของต้นไม้ไบนารี

ตัวอย่าง

มุมมองด้านล่างของทรีไบนารี

5 6 4 7

เข้าใกล้

วิธีนี้ง่ายมากเพราะเราได้แก้ปัญหาที่คล้ายกับสิ่งนี้แล้ว ปัญหามุมมองด้านบนของต้นไม้ไบนารีคล้ายกับที่เราต้องพิมพ์โหนดที่มองเห็นได้จากทิศทางข้างต้น แล้วเราจะแก้ปัญหาอย่างไร?

เราจำเป็นต้องใช้แนวคิดเรื่องระยะทางแนวนอนตรงนี้ เมื่อใดก็ตามที่เราเคลื่อนที่ไปในทิศทางซ้ายของโหนดเราจะลบออกจากระยะทางแนวนอนของโหนดปัจจุบัน ในทำนองเดียวกันถ้าเราเคลื่อนที่ไปในทิศทางที่ถูกต้องเราจะเพิ่ม 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;
}

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,int> m;
    queue<pair<int,node*>> q;
    q.push(make_pair(0, root));
    m[0] = root->data;
    while(!q.empty()){
        pair<int, node*> now = q.front();
        q.pop();

        m[now.first] = now.second->data;
        if(now.second->left)
        q.push(make_pair(now.first - 1, now.second->left));
        if(now.second->right)
        q.push(make_pair(now.first + 1, now.second->right));
    }
    for(auto x: m)
        cout<<x.second<<" ";
}
5 6 4 7

รหัส Java เพื่อพิมพ์มุมมองด้านล่างของทรีไบนารี

import java.util.*;

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

class Main{

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

  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, Integer> m = new TreeMap<Integer, Integer>();
      Queue<node> q = new LinkedList<node>();
      q.add(root);
      m.put(root.hd, root.data);
      while(!q.isEmpty()){
          node now = q.remove();

          m.put(now.hd, now.data);
          if(now.left != null){
          	now.left.hd = now.hd - 1;
          	q.add(now.left);
          }
          if(now.right != null){
          	now.right.hd = now.hd + 1;
          	q.add(now.right);
          }
      }
      for(Map.Entry<Integer, Integer> entry : m.entrySet())
          System.out.print(entry.getValue()+" ");
  }
}
5 6 4 7

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (NlogN)เนื่องจากเราได้สำรวจต้นไม้และได้อัปเดตค่าต่างๆ เนื่องจากเราใช้แผนที่การแทรกการลบและการค้นหาเสร็จสิ้นในเวลา O (logN)

ความซับซ้อนของอวกาศ

บน)มากที่สุดสามารถมี (N + 1) / 2 ในระดับสุดท้าย ดังนั้นความซับซ้อนของพื้นที่จึงเป็นเส้นตรง