uva12166专题

天平二叉树--uva12166 Equilibrium Mobile

用字符串形式给定一个天平,求出最少修改几个秤砣的质量,能使天平平衡。 别人非常非常非常神奇的题解! 1.秤砣都位于二叉树的叶子结点,即修改叶子结点使得天平平衡 2.至少有一个叶子结点不修改。 那么对于某个叶子结点,如果它不修改,其他所有结点参考它来平衡,它质量为w,深度为d,那么平衡后整个天平质量为w << d 3.对每个叶子结点为参考点的情况计算天平质量sumw,那可能有一些叶子结点计