최대 이진 트리

난이도 중급
자주 묻는 질문 아마존 구글 Microsoft 동네 짱
나무조회수 37
링크드 인버퍼레딧텀블러

이번에 문제, 우리는 크기 n의 배열 a []를 제공했습니다. 최대 값 만들기 이진 트리 배열에서 루트 노드를 반환합니다.

그것은에서 만들어집니다 정렬 다음 단계를 사용하십시오.

  • 트리의 루트 노드는 최대 값 주어진 배열에서.
  • 왼쪽 하위 트리는 배열의 최대 값 이전에 발생하는 값을 사용하여 만든 최대 트리입니다.
  • 오른쪽 하위 트리는 배열의 최대 값 이후에 발생하는 값을 사용하여 만든 최대 트리입니다.

 

최대 이진 트리핀

최대 이진 트리의 예

입력 : a [] = {3, 2, 1, 6, 0, 5}

출력 : 6

입력 : a [] = {3, 1, 7, 4}

출력 : 7

재귀 방법 최대 이진 트리

암호알고리즘

이것은 최대 바이너리 트리의 알고리즘입니다.

  1. 크기 n의 배열을 초기화합니다.
  2. 배열, 시작 인덱스 및 마지막 인덱스를 매개 변수로 받아들이는 이진 트리를 만드는 함수를 만듭니다.
  3. 시작 인덱스와 끝 인덱스가 같으면 NULL을 반환합니다.
  4. 그렇지 않으면 루트 노드의 배열에서 최대 요소를 찾습니다.
  5. 왼쪽 하위 트리의 경우 배열의 최대 요소 이전에 발생하는 요소에 대해 함수를 재귀 적으로 호출합니다.
  6. 마찬가지로 오른쪽 하위 트리의 경우 배열의 최대 요소 이후에 발생하는 요소에 대해 함수를 재귀 적으로 호출합니다.
  7. 루트 노드를 반환합니다.

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};

class Max{
    public:
    
    TreeNode* constructMaximumBinaryTree(int nums[], int n){
        return construct(nums, 0, n);
    }
    
    TreeNode* construct(int nums[], int l, int r){
        if (l == r)
            return NULL;
        int max_i = max(nums, l, r);
        TreeNode* root = new TreeNode(nums[max_i]);
        root->left = construct(nums, l, max_i);
        root->right = construct(nums, max_i + 1, r);
        return root;
    }
    
    int max(int nums[], int l, int r) {
        int max_i = l;
        for (int i = l; i < r; i++) {
            if (nums[max_i] < nums[i])
                max_i = i;
        }
        return max_i;
    }
};

int main(){
    Max m;
    
    int a[] = {3, 2, 1, 6, 0, 5};
    int n = sizeof(a)/sizeof(a[0]);
    TreeNode* root = m.constructMaximumBinaryTree(a, n);
    
    cout<<root->val;

    return 0; 
}
6

자바 프로그램

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int x){
        val = x;
    }
    
}
class Max{
    
    static TreeNode constructMaximumBinaryTree(int[] nums){
        return construct(nums, 0, nums.length);
    }
    static TreeNode construct(int[] nums, int l, int r) {
        if (l == r)
            return null;
        int max_i = max(nums, l, r);
        TreeNode root = new TreeNode(nums[max_i]);
        root.left = construct(nums, l, max_i);
        root.right = construct(nums, max_i + 1, r);
        return root;
    }
    static int max(int[] nums, int l, int r) {
        int max_i = l;
        for (int i = l; i < r; i++) {
            if (nums[max_i] < nums[i])
                max_i = i;
        }
        return max_i;
    }
    public static void main (String[] args) {
        int[] a = {3, 2, 1, 6, 0, 5};
        TreeNode root = constructMaximumBinaryTree(a);
        System.out.print(root.val + " ");
            
    }
}
6

복잡성 분석 최대 이진 트리

시간 복잡성

O(n2) (construct 함수는 n 번 호출됩니다. 각 레벨에서 최대 요소를 찾기 위해 n 개의 노드를 모두 탐색합니다. 최악의 경우 트리의 깊이는 최대 n이 될 수 있으므로 복잡성이 n2)

공간 복잡성

O(n) 최악의 경우 문자열의 크기가 n까지 커질 수 있기 때문입니다. 여기서 n은 주어진 입력 문자열의 크기입니다.

참조

링크드 인버퍼레딧텀블러
Translate »