This is an Amazon interview question for software engineer from careercup. Here is the original thread
Calculate and return array with a sum of every level.
For example,
1
2 3
4 5 1 2
Output should be [1, 5, 12].
For example,
1
2 3
4 5 1 2
Output should be [1, 5, 12].
2. C++ Implementation
// ********************************************************************************
// Implementation
// - Breadth first
// - Use null node as the dummy node to separate the levels
// ********************************************************************************
#include <cassert>
#include <memory>
#include <queue>
#include <stack>
#include <vector>
template<typename T>
struct TreeNode
{
TreeNode(const T& d)
: data(new T(d)), left(nullptr), right(nullptr)
{}
~TreeNode()
{
std::shared_ptr<T>().swap(data);
}
std::shared_ptr<T> data;
TreeNode* left;
TreeNode* right;
};
template<typename T>
struct TreeConstructionBFS
{
TreeConstructionBFS()
{}
TreeConstructionBFS(TreeNode<T>* p, bool left, int s, int e)
: parent(p), isLeftChild(left), start(s), end(e)
{}
TreeNode<T>* parent = nullptr;
bool isLeftChild = false;
int start = 0;
int end = -1;
};
// Free the resource
template<typename T>
void DeleteTree(TreeNode<T>** root)
{
TreeNode<T>* curNode = *root;
if (curNode != nullptr) {
TreeNode<T>* left = curNode->left;
TreeNode<T>* right = curNode->right;
delete curNode;
curNode = nullptr;
DeleteTree(&left);
DeleteTree(&right);
}
}
// Construct BST based on sorted input via BFS
template<typename T>
TreeNode<T>* ConstructTreeOnSortedValueBFS(const std::vector<T>& input)
{
if (input.empty()) {
return nullptr;
}
const int len = input.size();
int index = len >> 1;
TreeNode<T>* root = new TreeNode<T>(input[index]);
std::queue<TreeConstructionBFS<T>> nodesToBuild;
nodesToBuild.push(TreeConstructionBFS<T>(root, true, 0, index - 1));
nodesToBuild.push(TreeConstructionBFS<T>(root, false, index + 1, len - 1));
while (!nodesToBuild.empty()) {
const TreeConstructionBFS<T>& curCon = nodesToBuild.front();
if (curCon.start > curCon.end) {
if (curCon.isLeftChild) {
curCon.parent->left = nullptr;
}
else {
curCon.parent->right = nullptr;
}
}
else {
index = (curCon.start + curCon.end) >> 1;
TreeNode<T>* tempNode = new TreeNode<T>(input[index]);
if (curCon.isLeftChild) {
curCon.parent->left = tempNode;
}
else {
curCon.parent->right = tempNode;
}
nodesToBuild.push(TreeConstructionBFS<T>(tempNode,
true,
curCon.start,
index - 1));
nodesToBuild.push(TreeConstructionBFS<T>(tempNode,
false,
index + 1,
curCon.end));
}
nodesToBuild.pop();
}
return root;
}
// Implementation
template<typename T>
void GetSumOfEachLevelOfTree(TreeNode<T>* root, std::vector<T>& listOfLL)
{
if (root == nullptr) {
return;
}
std::queue<TreeNode<T>*> nodes;
nodes.push(root);
nodes.push(nullptr); // dummy node as separator of level
T sum(0);
while (!nodes.empty()) {
const TreeNode<T>* curNode = nodes.front();
nodes.pop();
if (curNode == nullptr) {
listOfLL.push_back(sum);
sum = 0;
if (nodes.empty()) {
break;
}
nodes.push(nullptr); // dummy node as separator of level
}
else {
sum += *curNode->data;
if (curNode->left != nullptr) {
nodes.push(curNode->left);
}
if (curNode->right != nullptr) {
nodes.push(curNode->right);
}
}
}
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestCasesOfSumOfEachLevelOfTree()
{
std::vector<int> testInput{ 1 };
TreeNode<int>* rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
std::vector<int> result;
GetSumOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 1);
assert(result[0] == 1);
DeleteTree(&rootBFS);
testInput = {1, 2};
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetSumOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 2);
assert(result[0] == 2);
assert(result[1] == 1);
DeleteTree(&rootBFS);
testInput = { 1, 2, 3 };
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetSumOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 2);
assert(result[0] == 2);
assert(result[1] == 4);
DeleteTree(&rootBFS);
testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetSumOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 4);
assert(result[0] == 6); // 6
assert(result[1] == 11);// 3, 8
assert(result[2] == 21); // 1, 4, 7, 9
assert(result[3] == 17);// 2, 5, 10
DeleteTree(&rootBFS);
}
No comments:
Post a Comment