MSRA : 二叉树上移石头

假设有一颗二叉树，已知这棵树的节点上不均匀的分布了若干石头，石头数跟这棵二叉树的节点数相同，石头只可以在子节点和父节点之间进行搬运，每次只能搬运一颗石头。请问如何以最少的步骤将石头搬运均匀，使得每个节点上的石头上刚好为1。

这么简单的题没人做啊，我做的是O(n)，但是节点里加了两个而外的记录变量，想看看其他人有没有更简洁的程序写法

回复 2# wwwyhx
也不算特别直接。有点想法但细节挺多的，感觉可以这样：
先预处理得到每个节点的左右两边子树的大小和现有的石头数目，然后分各种情况讨论。函数的参数是一个节点，要做的就是求出把这个节点以下的子树两边弄均匀并且把多余的石头放到根节点要用的最小步数。如果一边石头富裕另一边不够，就免不了要从一边移一些过去，可以当作是从左（右）子树的根节点直接移到右（左）子树的根节点，并且把值直接加到右子树上，然后再递归处理两边的情况。这里并不用管当前左右子树根节点的石头是否够用，因为递归的时候会保证把多余的放到根上，可以先“预支”。如果两边都缺就从根节点移一些分别到左右子树然后递归，如果两边都多就直接从左右子树的根节点移石头过来，然后递归。每次函数调用的时候该子树的总石头数总是够用的，因为如果不够的话在外层的时候已经调整过了。

后来又想了下，可以非常简化，代码如下，欢迎指出bug：

1. int MoveStone(node *root, int &moves)
   
2. {
   
3.         int l, r, ls, rs;
   
4.         if(!root)
   
5.                 return (moves=0);
   
6.         l = MoveStone(root->left, ls);
   
7.         r = MoveStone(root->right, rs);
   
8.         moves = abs(l) + abs(r) + ls + rs;
   
9.         return l+r+root->stone-1;
   
10. }

复制代码

核心思想在于“预支”。把不均匀的部分（哪怕是负的）都放到当前的根节点，上层自然会做出调整。由于题目条件的保证，到整个树的根节点肯定会是均匀的。

后来又想了下，可以非常简化，代码如下，欢迎指出bug：

核心思想在于“预支”。把不均匀的部分（哪怕是负的）都放到当前的根节点，上层自然会做出调整。由于题目条件的保证，到整个树的根节点肯定会是均匀的。
darksteel 发表于 2011-5-15 09:48

感觉是权值绝对值的思想吧。
没错，如果题目问最少多少步可以移好是个很简洁的解法，问题是题目问的是怎么移？

回复 5# wwwyhx
要一步步写出怎么移确实比较麻烦。思路还是可以用上面那个思路，但步骤的先后顺序就要注意，不能随便预支了。必须保证多余的先移到位，然后才能移给那些不够的。细节比较多但好像还是可以通过这条路走通

回复  wwwyhx
要一步步写出怎么移确实比较麻烦。思路还是可以用上面那个思路，但步骤的先后顺序就要注意，不能随便预支了。必须保证多余的先移到位，然后才能移给那些不够的。细节比较多但好像还是可以通过这条路走通
darksteel 发表于 2011-5-15 11:48

    做了两步，一步是move up, 从底层节点开始把每个子树多余的石头上移，每个子树的石头<=子树节点的个数，第二步move down, 从根节点开始把多余的下分。不知道有没有更简洁的

回复 7# wwwyhx
有没有可能所有的石头淤积在中间某些地方，根和叶子都比较空呢？

回复  wwwyhx
有没有可能所有的石头淤积在中间某些地方，根和叶子都比较空呢？
darksteel 发表于 2011-5-15 11:54

    就算有可能，也是不能避免的。为什么会存在非最简路径呢，就是因为移动存在重复路径，比如a->b,b->c,c->d,d->c,c->f, 实际上只用a->b,b->c,c->f就可以了，自下而上由子树权值(子树节点和子树石头的差)的角度来考虑是不会有重复路径的。出发点是后续的思想，对任何一颗子树来说，如果我左子树平衡了，右子树平衡了，根节点怎么调整，根节点多的往上推，少的向上要？？我分别用用push up, 和move down就是为了让根节点向上要的时候一定会在父节点有多的，不用拐弯什么的，否则又麻烦，时间复杂度会变nlogn

回复 9# wwwyhx
差不多明白了，想法还是挺有道理的。先往上推一遍，这样就能保证往下推的时候总是有富裕，两遍之后就均匀了。。实现上会稍微麻烦点，push up和move down应该都可以通过递归来实现，节点可能不需要多余的变量来保存信息