เส้นทแยงมุมของต้นไม้ไบนารี


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน ข้อเท็จจริง fanatics โฟร์ไคต์ คำพยากรณ์ payu Quora
ต้นไม้ไบนารี ต้นไม้ ทรีทราเวอร์ซัล

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

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

ตัวอย่าง

เส้นทแยงมุมของต้นไม้ไบนารี

2 7
3 4
5 6

คำอธิบาย

เส้นทแยงมุมแรกมีโหนด 2, 7 อยู่ในนั้น จากนั้นเส้นทแยงมุมที่สองจะมี 3, 4 ในทำนองเดียวกันสำหรับเส้นทแยงมุมที่สาม 5, 6 ดังนั้นผลลัพธ์จึงถูกพิมพ์ในลักษณะที่องค์ประกอบจากเส้นทแยงมุมเดียวกันมีอยู่ในบรรทัดเดียวกัน

เข้าใกล้

เส้นทแยงมุมของต้นไม้ไบนารี

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

เราจะทำการข้ามตามลำดับของต้นไม้ไบนารี ในขณะที่ทำสิ่งนี้เราจะติดตามระยะทางในแนวทแยง เมื่อใดก็ตามที่เราเคลื่อนที่ไปในทิศทางซ้ายเราจะเพิ่ม 1 เข้าไปในระยะทแยงมุมและถ้าเราเคลื่อนที่ไปในทิศทางที่ถูกต้องเราจะไม่เพิ่มมูลค่าใด ๆ ให้กับระยะทาง ดังนั้นในขณะที่ทำสิ่งนี้เราจะติดตามโหนดที่เข้าชมในไฟล์ แผนที่. เราจะสร้างแผนที่ที่มีระยะทแยงมุมเป็นกุญแจสำคัญและเวกเตอร์เป็นค่า เพราะเราจะเพิ่มโหนดที่มีระยะทแยงมุมในเวกเตอร์ และในขณะที่เราได้ข้ามผ่านทั้งหมด ต้นไม้. หลังจากการข้ามผ่านเราจะเก็บโหนดไว้ในเวกเตอร์ตามระยะทางในแนวทแยง

หลังจากการคำนวณทั้งหมดนี้เพียงแค่พิมพ์องค์ประกอบในแผนที่ในขณะที่แยกโหนดออกจากเวกเตอร์แต่ละตัว

รหัส C ++ เพื่อพิมพ์ Diagonal Traversal ของ Binary Tree

#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 เพื่อพิมพ์ Diagonal Traversal ของ Binary Tree

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)

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

บน), เพราะเรากำลังจัดเก็บโหนดทั้งหมดในแผนที่ ความซับซ้อนของพื้นที่เป็นเชิงเส้น