Cây nhị phân tối đa trong C ++

Giả sử chúng ta có một mảng số nguyên. Tất cả các phần tử trong mảng đó là duy nhất. Tòa nhà cây tối đa trên mảng này được định nghĩa như sau -

• Gốc sẽ chứa số lượng tối đa trong mảng.

• Cây con bên trái là cây tối đa được tạo từ phía bên trái của mảng con chia cho số lớn nhất.

• Cây con bên phải là cây tối đa được tạo từ phía bên phải của mảng con chia cho số lớn nhất.

Chúng ta phải xây dựng cây nhị phân tối đa. Vì vậy, nếu đầu vào là:[3,2,1,6,0,5], thì đầu ra sẽ là -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức có tên là giải quyết (), phương thức này sẽ nhận danh sách và các giá trị bên trái và bên phải. Hàm sẽ hoạt động như sau -

• nếu left> right, thì trả về null

• maxIndex:=left và maxVal:=nums [left]

• cho tôi trong phạm vi từ trái + 1 sang phải

  • nếu maxVal

• xác định một nút có giá trị maxVal

• bên trái của nút:=giải quyết (nums, left, maxIndex - 1)

• bên phải của nút:=giải quyết (nums, maxIndex + 1, bên phải)

• nút trả lại

• Phương thức giải quyết sẽ được gọi từ phần chính là:giải quyết (nums, 0, độ dài của mảng nums - 1)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

4 3 2 7 1 6