차례
문제 정책
"바이너리 트리에서 최대 레벨 합계 찾기"문제는 이진 트리 양수 및 음수 노드로 이진 트리에서 수준의 최대 합계를 찾습니다.
예
입력
7
설명
첫 번째 수준 : 합계 = 5
두 번째 수준 : 합계 = (-2 + 6) = 4
세 번째 수준 : 합계 = (11 + (-5) + 1) = 7
네 번째 수준 : 합계 = (3 + (-3)) = 0
최대 합계 = 7
이진 트리에서 최대 레벨 합계를 찾는 알고리즘
아이디어는 레벨 순서 순회를 수행하고 각 레벨에 대해 해당 레벨의 모든 노드의 합계를 계산하는 것입니다. 합계가 최대 합계보다 크면 최대 합계를 업데이트합니다.
- 만들기 변발을 클릭하고 루트 노드를 큐에 푸시합니다. 변수 초기화 최대 합계 음의 무한대로.
- 대기열이 비어 있지 않은 동안 3 단계와 4 단계를 반복하십시오.
- 이 순간 대기열에는 한 수준이 있습니다. 이름이 지정된 변수 초기화 크기 대기열의 크기와 변수 합계는 0입니다.
- i = 0에서 크기까지 루프를 실행하고 각 반복에서 큐에서 요소를 팝 아웃합니다. 이 요소의 값을 변수 합계에 추가하고 튀어 나온 노드의 자식을 큐에 푸시합니다. 합계가 maxSum보다 크면 루프 끝에서 maxSum을 합계로 업데이트합니다.
- 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
복잡성 분석
시간 복잡성
의 위에), 단순히 모든 트리 요소를 순회하고 대기열에 두 번 푸시했기 때문입니다. 따라서 시간 복잡도는 선형입니다.
공간 복잡성
의 위에), 큐를 사용하여 각 레벨의 요소를 저장했기 때문입니다. 공간 복잡성도 선형입니다.
