ความกว้างสูงสุดของไบนารีทรีใน C++

สมมติว่าเรามีไบนารีทรี เราต้องกำหนดฟังก์ชันเพื่อให้ได้ความกว้างสูงสุดของต้นไม้ที่กำหนด ในที่นี้ความกว้างของต้นไม้คือความกว้างสูงสุดในทุกระดับ เราจะพิจารณาว่าไบนารีทรีมีโครงสร้างเหมือนกับต้นไม้ไบนารีแบบเต็ม แต่บางโหนดเป็นโมฆะ ความกว้างของระดับหนึ่งคือความยาวระหว่างโหนดปลายสุด (โหนดที่ไม่ใช่ค่าว่างทางซ้ายสุดและขวาสุดในระดับ โดยที่โหนดว่างระหว่างโหนดปลายสุดจะถูกนับด้วยการคำนวณความยาวด้วย) ดังนั้นถ้าต้นไม้เป็นเหมือน −

จากนั้นความกว้างสูงสุดคือ 4 เนื่องจากโหนดของเลเยอร์สุดท้ายคือ [5,3,null,9]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ตอบ :=1, ขนาด :=0

• กำหนดคิวสองสิ้นสุด q ที่เราจะเก็บ (โหนด, ค่า) คู่

• แทรก (root, 1) ลงใน q

• ในขณะที่ q ไม่ว่างเปล่า

  • size :=ขนาดของ q

  • กำหนดสกุลเงินคู่ (โหนด, ค่า)

  • ถ้าขนาดเป็น 1 ดังนั้น (โหนดขององค์ประกอบด้านหน้า 1) เป็น q ให้ลบองค์ประกอบออกจาก q

  • ในขณะที่ขนาดไม่ใช่ 0

    • curr :=องค์ประกอบด้านหน้าของ q ลบองค์ประกอบด้านหน้าออกจาก q

    • หากโหนด curr เหลือไม่เป็นโมฆะ

      • สร้าง (ด้านซ้ายของโหนดปัจจุบัน ค่า 2* ของสกุลเงิน) และแทรกลงใน q

    • ถ้าทางขวาของโหนดเคอร์รไม่เป็นโมฆะ

      • สร้าง (ทางขวาของโหนดปัจจุบัน ค่า 2* ของเคอร์เซอร์ + 1) แล้วแทรกลงใน q

    • ถ้าขนาด q> 1 แล้ว

      • ans :=สูงสุดของ ans ค่าขององค์ประกอบสุดท้ายใน q – ค่าขององค์ประกอบแรกของ q + 1

    • ขนาด :=ขนาด – 1

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
      TreeNode *root = new TreeNode(v[0]);
      for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
   int widthOfBinaryTree(TreeNode* root) {
      int ans = 0;
      deque < pair <TreeNode*, int> > q;
      q.push_back({root,1});
      ans = 1;
      int size;
      while(!q.empty()){
         size = q.size();
         pair <TreeNode*, int> curr;
         if(size == 1){
            q.push_back({q.front().first, 1});
            q.pop_front();
         }
         while(size--){
            curr = q.front();
            q.pop_front();
            if(curr.first->left){
               q.push_back({curr.first->left, 2 * curr.second});
            }
            if(curr.first->right){
               q.push_back({curr.first->right, 2 * curr.second + 1});
            }
         }
         if(q.size() > 1)
            ans = max(ans, q.back().second - q.front().second + 1);
      }
      return ans;
   }
};
main(){
   vector<int> v = {1,3,2,5,3,NULL,9};
   TreeNode *root = make_tree(v);
   Solution ob;
   cout << (ob.widthOfBinaryTree(root));
}

อินพุต

[1,3,2,5,3,null,9]

ผลลัพธ์

4