今天跟同学讨论面试题，又提到这个题了。之前在论坛里有人说是MSRA用过的面试题。题是这样的，假设有1棵二叉树，已知这棵树的节点上不均匀地分布了若干石头，石头数跟这棵二叉树的节点数相同。石头只能在子节点和父节点之间搬迁，每次只能搬运一块石头。请问如何以最少的步骤将石头搬运均匀，使得每个节点上的石头刚好为1。
我想到的是用后根遍历解，除了递归不需要额外空间，时间复杂度O(n)。
struct node
{
int id;
int stone;
node *left;
node *right;
};
int move_stone(node *root, int &min_step)
{
if (root != NULL)
{
int left_needs = move_stone(root->left, min_step);
int right_needs = move_stone(root->right, min_step);
min_step += abs(left_needs);
min_step += abs(right_needs);
return -(root->stone - left_needs - right_needs - 1);
}
return 0;
}