ทรีไบนารีสูงสุดใน C++

สมมติว่าเรามีอาร์เรย์จำนวนเต็ม องค์ประกอบทั้งหมดในอาร์เรย์นั้นไม่ซ้ำกัน การสร้างต้นไม้สูงสุดในอาร์เรย์นี้ถูกกำหนดดังนี้ -

• รูทจะเก็บจำนวนสูงสุดไว้ในอาร์เรย์

• ทรีย่อยด้านซ้ายเป็นทรีสูงสุดที่สร้างจากด้านซ้ายของ subarray หารด้วยจำนวนสูงสุด

• ทรีย่อยด้านขวาคือทรีสูงสุดที่สร้างจากด้านขวาของอาร์เรย์ย่อยหารด้วยจำนวนสูงสุด

เราต้องสร้างไบนารีทรีสูงสุด ดังนั้นหากอินพุตมีลักษณะดังนี้:[3,2,1,6,0,5] ผลลัพธ์จะเป็น −

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

• กำหนดวิธีการที่เรียกว่าแก้ปัญหา () ซึ่งจะรับรายการและค่าซ้ายและขวา ฟังก์ชันจะทำงานดังนี้ −

• ถ้า left> right ให้คืนค่า null

• maxIndex :=left และ maxVal :=nums[left]

• สำหรับฉันอยู่ในช่วงซ้าย + 1 ไปขวา

  • ถ้า maxVal

• กำหนดโหนดที่มีค่า maxVal

• ด้านซ้ายของโหนด :=แก้ (nums, left, maxIndex - 1)

• ด้านขวาของโหนด :=แก้ (nums, maxIndex + 1, ขวา)

• โหนดกลับ

• วิธีการแก้ปัญหาจะถูกเรียกจากส่วนหลักดังนี้:Solve(nums, 0, length of nums array - 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;
}
void inord(TreeNode *root){
   if(root != NULL){
      inord(root->left);
      cout << root->val << " ";
      inord(root->right);
   }
}
class Solution {
   public:
   TreeNode* solve(vector <int>& nums, int left, int right){
      if(left>right)return NULL;
      int maxIndex = left;
      int maxVal = nums[left];
      for(int i = left + 1; i <= right; i++){
         if(maxVal < nums[i]){
            maxVal = nums[i];
            maxIndex = i;
         }
      }
      TreeNode* node = new TreeNode(maxVal);
      node->left = solve(nums, left, maxIndex - 1);
      node->right = solve(nums, maxIndex + 1, right);
      return node;
   }
   TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
      return solve(nums, 0, nums.size() - 1);
   }
};
main(){
   vector<int> v = {4,3,2,7,1,6};
   Solution ob;
   inord(ob.constructMaximumBinaryTree(v));
}

อินพุต

[3,2,1,6,0,5]

ผลลัพธ์

4 3 2 7 1 6