이진 트리에서 최대 레벨 합계 찾기

난이도 중급
자주 묻는 질문 아마존
이진 트리 폭 우선 검색 나무 트리 순회조회수 29

문제 정책

"바이너리 트리에서 최대 레벨 합계 찾기"문제는 이진 트리 양수 및 음수 노드로 이진 트리에서 수준의 최대 합계를 찾습니다.

입력
이진 트리에서 최대 레벨 합계 찾기

7

설명
첫 번째 수준 : 합계 = 5
두 번째 수준 : 합계 = (-2 + 6) = 4
세 번째 수준 : 합계 = (11 + (-5) + 1) = 7
네 번째 수준 : 합계 = (3 + (-3)) = 0
최대 합계 = 7

이진 트리에서 최대 레벨 합계를 찾는 알고리즘

아이디어는 레벨 순서 순회를 수행하고 각 레벨에 대해 해당 레벨의 모든 노드의 합계를 계산하는 것입니다. 합계가 최대 합계보다 크면 최대 합계를 업데이트합니다.

  1. 만들기 변발을 클릭하고 루트 노드를 큐에 푸시합니다. 변수 초기화 최대 합계 음의 무한대로.
  2. 대기열이 비어 있지 않은 동안 3 단계와 4 단계를 반복하십시오.
  3. 이 순간 대기열에는 한 수준이 있습니다. 이름이 지정된 변수 초기화 크기 대기열의 크기와 변수 합계는 0입니다.
  4. i = 0에서 크기까지 루프를 실행하고 각 반복에서 큐에서 요소를 팝 아웃합니다. 이 요소의 값을 변수 합계에 추가하고 튀어 나온 노드의 자식을 큐에 푸시합니다. 합계가 maxSum보다 크면 루프 끝에서 maxSum을 합계로 업데이트합니다.
  5. maxSum을 반환합니다.

설명

위의 예에서 트리를 고려하십시오.

단계 1

큐를 만들고 루트를 푸시합니다. 변수 maxSum을 음의 무한대로 초기화합니다.
queue = 5 및 maxSum = -infinity

단계 2

대기열이 비어 있지 않은 상태에서 3 단계와 4 단계를 반복합니다.

3 단계와 4 단계

반복 1
크기 = 1, 합계 = 0
큐에서 모든 요소를 ​​제거하고 각 요소의 값을 합산에 더한 다음 모든 요소의 자식을 큐에 푸시합니다.
합계 = 5, 대기열 = -2-> 6
maxSum을 업데이트하므로 maxSum = 5

반복 2
크기 = 2, 합계 = 0
큐에서 모든 요소를 ​​제거하고 각 요소의 값을 합산에 더한 다음 모든 요소의 자식을 큐에 푸시합니다.
합계 = (-2 + 6) = 4, 대기열 = 11-> -5-> 1
maxSum을 업데이트하므로 maxSum = 5

반복 3
크기 = 3, 합계 = 0
큐에서 모든 요소를 ​​제거하고 각 요소의 값을 합산에 더한 다음 모든 요소의 자식을 큐에 푸시합니다.
합계 = (11 + (-5) + 1) = 7, 대기열 = 3-> -3
maxSum을 업데이트하므로 maxSum = 7

반복 4
크기 = 2, 합계 = 0
큐에서 모든 요소를 ​​제거하고 각 요소의 값을 합산에 더한 다음 모든 요소의 자식을 큐에 푸시합니다.
합계 = (3 + (-3)) = 0, 대기열 = null
maxSum을 업데이트하므로 maxSum = 7

큐가 비워 지므로 중지하고 레벨의 최대 합계는 7입니다.

암호

이진 트리에서 최대 레벨 합계를 찾는 Java 코드

import java.util.LinkedList;
import java.util.Queue;

class FindMaximumLevelSumInBinaryTree {
    // class representing node of binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int maxLevelSum(Node root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }       
        // create a queue and push root to it
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        // initialize maxSum as negative infinity 
        int maxSum = Integer.MIN_VALUE;
        
        // while queue is not empty
        while (!queue.isEmpty()) {
            // At this moment the queue contains one level in it
            // initialize size as size of queue
            int size = queue.size();
            // initialize sum as 0, this represents the sum of a level
            int sum = 0;
            // run a loop from 0 to size
            for (int i = 0; i < size; i++) {
                // remove an element from queue
                Node curr = queue.poll();
                // add the value of current element to sum
                sum += curr.data;
                
                // push the children of current element to queue
                if (curr.left != null)
                    queue.add(curr.left);
                
                if (curr.right != null)
                    queue.add(curr.right);
            }

            // update max sum
            maxSum = Math.max(maxSum, sum);
        }
        
        // return max sum
        return maxSum;
    }

    public static void main(String[] args) {
        // Example tree
        Node root = new Node(5);
        root.left = new Node(-2);
        root.right = new Node(6);
        root.left.left = new Node(11);
        root.right.left = new Node(-5);
        root.right.right = new Node(1);
        root.right.right.left = new Node(3);
        root.right.right.right = new Node(-3);

        System.out.println(maxLevelSum(root));
    }
}
7

이진 트리에서 최대 레벨 합계를 찾는 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

// class representing node of a binary tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node with data d
Node* newNode(int d) {
    Node *node = new Node(d);
    return node;
}

int maxLevelSum(Node *root) {
    if (root == NULL) {
        return INT_MIN;
    }
    
    // create a queue and push root to it
    queue<Node*> q;
    q.push(root);
    // initialize maxSum as negative infinity
    int maxSum = INT_MIN;
    
    // while queue is not empty
    while (!q.empty()) {
        // At this moment the queue contains one level in it
        // initialize size as size of queue
        int size = q.size();
        // initialize sum as 0, this represents the sum of a level
        int sum = 0;
        
        // run a loop from 0 to size
        for (int i = 0; i < size; i++) {
            // remove an element from queue
            Node *curr = q.front();
            q.pop();
            // add the value of current element to sum
            sum += curr->data;
            
            // push the children of current element to queue
            if (curr->left != NULL)
                q.push(curr->left);
                
            if (curr->right != NULL)
                q.push(curr->right);
        }
        
        // update max sum
        maxSum = std::max(maxSum, sum);
    }
    
    // return max sum
    return maxSum;
}

int main() {
    // Example tree
    Node *root = newNode(5);
    root->left = newNode(-2);
    root->right = newNode(6);
    root->left->left = newNode(11);
    root->right->left = newNode(-5);
    root->right->right = newNode(1);
    root->right->right->left = newNode(3);
    root->right->right->right = newNode(-3);
    
    cout<<maxLevelSum(root)<<endl;
    
    return 0;
}
7

복잡성 분석

시간 복잡성

의 위에), 단순히 모든 트리 요소를 순회하고 대기열에 두 번 푸시했기 때문입니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

의 위에), 큐를 사용하여 각 레벨의 요소를 저장했기 때문입니다. 공간 복잡성도 선형입니다.

Translate »