// Given a binary tree, return the level of the tree with minimum sum.
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
class Node
{
public:
int value;
Node* left = nullptr;
Node* right = nullptr;
Node* parent = nullptr;
Node(int newValue, Node* nodeParent = nullptr)
{
value = newValue;
parent = nodeParent;
}
};
int maxLevelSum(Node * root)
{
if (root == NULL)
return 0;
int currentLevel = 0;
int minLevel = 1;
int minSum = root->value;
queue<Node*> q;
q.push(root);
while (!q.empty())
{
// get queue size when the order traversal is finished
int count = q.size();
// iterate through the queue
int sum = 0;
// increase the level were at
++currentLevel;
while (count--)
{
Node *temp = q.front();
q.pop();
// add current node value to the sum
sum += temp->value;
// enqueue both children of the current node
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
// check for the minimum total sum
if (sum < minSum)
{
minSum = sum;
minLevel = currentLevel;
}
}
return minLevel;
}
Node* generateTree()
{
Node* head = new Node(21);
head->left = new Node(6, head);
head->right = new Node(9, head);
head->left->left = new Node(1, head->left);
head->left->right = new Node(1, head->left);
head->right->left = new Node(2, head->right);
head->right->right = new Node(9, head->right);
cout << "Tree constructed" << endl;
return head;
}
int main()
{
Node* tree = generateTree();
auto result = maxLevelSum(tree);
cout << "Min Level is: " << result << endl;
return 0;
}
Comentarios