C++의 최대 이진 트리

정수 배열이 있다고 가정합니다. 해당 배열의 모든 요소는 고유합니다. 이 배열에 대한 최대 트리 구축은 다음과 같이 정의됩니다. -

• 루트는 배열의 최대 수를 유지합니다.

• 왼쪽 하위 트리는 하위 배열의 왼쪽에서 구성된 최대 트리를 최대 수로 나눈 값입니다.

• 오른쪽 하위 트리는 하위 배열의 오른쪽에서 구성된 최대 트리를 최대 수로 나눈 값입니다.

우리는 최대 이진 트리를 구성해야 합니다. 따라서 입력이 [3,2,1,6,0,5]와 같으면 출력은 -

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• solve()라는 메서드를 정의하면 목록과 왼쪽 및 오른쪽 값이 사용됩니다. 이 기능은 다음과 같이 작동합니다 -

• 왼쪽> 오른쪽이면 null 반환

• maxIndex :=왼쪽 및 maxVal :=nums[left]

• 왼쪽 + 1에서 오른쪽 범위의 i에 대해

  • maxVal

• 값이 maxVal인 노드 정의

• 노드 왼쪽 :=solve(nums, left, maxIndex - 1)

• 노드 오른쪽 :=solve(nums, maxIndex + 1, right)

• 반환 노드

• solve 메소드는 다음과 같이 메인 섹션에서 호출됩니다: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