求职面试问题变得更难了，除了根之外，其他都检查过了？

Question

在一次面试中，我被问到了这个问题，而一开始看起来真的很容易，当我变得更深的时候，对我来说，这对我来说是不可能的。

请求：

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

如果根没有子返回-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. ，我不是所有孩子的体重之和。--

1. 当我到达叶孩子时，我正在总结-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;
}