求职面试问题变得更难了，除了根以外都查

Question

我在一次采访中遇到了这个问题，虽然一开始我觉得很容易，但当我深入研究时，我觉得有很多边缘案例是不可能的。

需求：

想象一个树，每个节点可以有0到10个子节点，每个子节点都有自己的权重，编写一个函数，执行以下操作：

1. 如果根没有子项，则返回-1
2. 否则，返回树的所有子级(除了根本身(的权重之和

我尝试了一些类似的东西：

int my_func(node *root) {
if (root->isleaf())
{
return -1;
}
int result = 0;
for (int i = 0; i < root->num_of_children(); ++i)
{
result += my_func(root->child[i]);
}
return result;
}

但这真的很糟糕，原因有二：

1. 我不是在求所有孩子的权重。

2. 当我到达leaf-child时，我正在求和-1，而我应该加0。

Answer 1

创建一个新函数，将其委托给处理根没有子项的情况的函数，并在计算和后删除根的权重。您还忘记在原始函数中添加权重。您可以通过在添加其余内容之前将result设置为root->weight来修复此问题。

int sumOfWeightsExceptRoot(node* root) {
if (!root || root->isLeaf())
return -1;
return my_func(root) - root->weight;
}
int my_func(node* root) {
if (!root)
return 0;
int result = root->weight;
for (int i = 0; i < root->num_of_children(); ++i) {
result += my_func(root->child[i]);
}
return result;
}

迭代版本：

int sumOfWeightsExceptRoot(node* root) {
if (!root || root->isLeaf())
return -1;
std::stack<node*> s;
s.push(root);
int result = -root->weight;
while (!s.empty()) {
node* ptr = s.top(); s.pop();
result += ptr->weight;
for (int i = 0; i < ptr->num_of_children(); i++) {
s.push(ptr->child[i]);
}
}
return result;
}