剧透警告：包括完整的解决方案（读取输入除外）
这个问题很古老，看起来很有趣，所以我只是在几个类似提示的开头段落之后去解决了它（在C中，而不是像这样被标记的PHP）。我使用了冗长的变量名称并进行了注释，因此它应该作为伪代码工作。我打算写类似C的伪代码，但从来没有遇到过任何值得总结的东西。
此问题的主要复杂之处在于您不能使用二叉树，因为单个天平可以在其中一个或两个平移上有多个其他天平。这里最简单的方法可能是节点的链接列表，其中每个节点都有左子节点和右子节点，还有一个同级指针。若要获取位于余额左平移上的所有余额，请遍历同级指针的链接列表，从您正在查看的余额的节点的左侧子级开始。
由于输入格式为所有余额分配数字，因此最简单的方法是将这些索引用于结构数组。如果可以假设余额少于 2^31，则可以使用 32 位 int 而不是 64 位指针来节省内存。（负索引是空的哨兵，就像基于指针的树/列表实现中的 NULL 指针一样）
struct balance {
// weights sitting directly on the pans of this balance
float weight_left, weight_right; // or unsigned int; the question only said the balance-count was an int. I assumed the balance-IDs were int, too
// optionally: float adjustment; // For recording our changes. negative or positive for adding to left or right balance.
// references to other balances: negative means empty-list, otherwise index into an array.
int next; // linked-list of sibling balances on the same pan of a parent
int left, right; // list-heads for balances on the left and right pan
};
当他们说你应该给“最低”的余额增加重量时，我猜他们的意思是根在底部。它不是一棵悬挂在某物上的悬空天平树。
您可以向已携带天平的天平添加重量。因此，在树叶的空平底锅上增加重量并不复杂。（这需要以一种保持每个子树单独平衡的方式划分权重）。
因此，以递归方式解决这看起来非常简单。
- 子树可以单独平衡，而无需有关任何其他余额的任何信息。
- 砝码和其他天平平衡的组合构成左右平底锅的负载并不重要。你只需要这两个总数。通过将重量直接添加到较轻的平底锅中来平衡。
- 在平衡其所有子树后平衡余额。您可以在平衡子树的同时将子树的权重相加。
所以算法是：
static const float BALANCE_WEIGHT = 10.0f;
// return total weight of the balance and everything on it, including the 10.0f that this balance weighs
// modify the .weight_left or .weight_right of every node that needs it, in the subtrees of this node
float balance(struct balance storage[], int current)
{
float lweight = 0, rweight = 0;
// C++ can make this more readable:
// struct balance &cur = storage[current];
// loop over all the left and then right children, totalling them up
// depth-first search, since we recurse/descend before doing anything else with the current
for (int i = storage[current].left ; i >= 0 ; i = storage[i].next )
lweight += balance(storage, i);
for (int i = storage[current].right; i >= 0 ; i = storage[i].next )
rweight += balance(storage, i);
lweight += storage[current].weight_left;
rweight += storage[current].weight_right;
float correction = fabsf(rweight - lweight);
// modify the data structure in-place with the correction.
// TODO: print, or add to some other data structure to record the changes
if (lweight < rweight) {
storage[current].weight_left += correction;
} else {
storage[current].weight_right += correction;
}
return BALANCE_WEIGHT + rweight + lweight + correction;
}
要记录您所做的更改，请在数据结构中使用额外的字段，或者在从深度优先平衡中恢复时销毁原始数据（因为不再需要它）。例如，如果左侧需要添加重量，则存储，否则反其道而行之。.weight_left = correction; .weight_right = 0;
如果存在全局数组，则此实现将使用较少的堆栈空间，而不是每个递归调用都必须传递指针。这是一个额外的值，必须在寄存器调用ABI中保存/恢复，并在堆栈调用ABI（如32bit x86）中直接占用额外空间。storage
所有涉及当前节点的计算都发生在最后，而不是在开始时读取它们，然后必须重新读取它们以进行+=读取 - 修改 - 写入。编译器无法进行此优化，因为它无法知道数据结构没有周期，从而导致修改其中一个权重。weight_leftweight_rightbalance(subtree)
出于某种原因，x86 gcc 5.2 将其编译为非常庞大的代码。它更理智与. 确实没问题，但错过了一些优化。-O3-O2clang-O3
