C++での最大二分木

整数配列があるとします。その配列内のすべての要素は一意です。この配列での最大ツリー構築は、次のように定義されます-

• ルートは配列内の最大数を保持します。

• 左側のサブツリーは、サブアレイの左側を最大数で割って構築された最大ツリーです。

• 右側のサブツリーは、サブアレイの右側を最大数で割って構築された最大ツリーです。

最大の二分木を構築する必要があります。したがって、入力が[3,2,1,6,0,5]の場合、出力は-

これを解決するには、次の手順に従います-

• Solve（）というメソッドを定義します。これにより、リストと左右の値が取得されます。関数は次のように機能します-

• 左>右の場合、nullを返します

• maxIndex：=leftおよびmaxVal：=nums [left]

• 左+1から右の範囲のiの場合

  • maxVal

• 値maxVal

  でノードを定義します

• ノードの左側：=solve（nums、left、maxIndex-1）

• ノードの右側：=resolve（nums、maxIndex + 1、right）

• リターンノード

• 解決メソッドは、メインセクションから次のように呼び出されます。solve（nums、0、nums配列の長さ-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