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

Giả sử chúng ta có một nút gốc của cây tối đa:Cây tối đa là cây mà mọi nút đều có giá trị lớn hơn bất kỳ giá trị nào khác trong cây con của nó. Giả sử chúng ta có một phương thức gọi là construct (). Điều này có thể tạo một gốc từ một danh sách A. Phương thức construct () giống như -

• Nếu danh sách A trống, trả về null.

• Ngược lại, đặt A [i] là phần tử lớn nhất của danh sách A. Sau đó, tạo một nút gốc với giá trị A [i].

• Con bên trái của root sẽ là cấu trúc ([A [0], A [1], ..., A [i-1]])

• Con bên phải của root sẽ là cấu trúc ([A [i + 1], A [i + 2], ..., A [n - 1]]) [n là độ dài của A]

• Trả lại thư mục gốc.

Lưu ý rằng chúng ta không được cung cấp A một cách trực tiếp, chỉ có một nút gốc root =construct (A). Bây giờ, giả sử B là một bản sao của A với giá trị được thêm vào nó. Đảm bảo rằng B có các giá trị duy nhất. Chúng ta phải dựng (B). Nếu giá trị là 5 và cây đầu vào giống như -

Cây đầu ra giống như -

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

• định nghĩa một phương thức đệ quy giải quyết (). Đây là root và val

• Nếu cây trống, hãy tạo một nút mới với giá trị val và trả về nút đó

• if value của root

  • temp:=nút mới có giá trị là val

  • left of temp:=root

  • trở lại nhiệt độ

• quyền gốc:=giải quyết (quyền gốc, val)

• trả về thư mục gốc

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 tree_level_trav(TreeNode*root){
   if (root == NULL) return;
   cout << "[";
   queue<TreeNode *> q;
   TreeNode *curr;
   q.push(root);
   q.push(NULL);
   while (q.size() > 1) {
      curr = q.front();
      q.pop();
      if (curr == NULL){
         q.push(NULL);
      }
      else {
         if(curr->left)
            q.push(curr->left);
         if(curr->right)
            q.push(curr->right);
         if(curr == NULL || curr->val == 0){
            cout << "null" << ", ";
         }else{
            cout << curr->val << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
      if(!root)return new TreeNode(val);
      if(root->val < val){
         TreeNode* temp = new TreeNode(val);
         temp->left = root;
         return temp;
      }
      root->right = insertIntoMaxTree(root->right, val);
      return root;
   }
};
main(){
   vector<int> v = {4,1,3,NULL,NULL,2};
   TreeNode *root = make_tree(v);
   Solution ob;
   tree_level_trav(ob.insertIntoMaxTree(root, 5));
}

Đầu vào

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

Đầu ra

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