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

Question

假设有一颗二叉树,已知这棵树的节点上不均匀的分布了若干石头,石头数跟这棵二叉树的节点数相同,石头只可以在子节点和父节点之间进行搬运,每次只能搬运一颗石头.请问如何以最少的步骤将石头搬运均匀,使得每个节点上的石头上刚好为1.输入：二叉树的总结点数N,每个节点的父节点ID,每个节点上初始含有的石头数.
最小运输步骤数
依次列出所有步骤,每个步骤的描述为：源节点ID1 --> 目标节点ID2,表示从ID1往ID2运输一粒石头.

Answer 1

n0=n2+1(你可以把二叉树想象拉成一个直角管道的形状就好理解了),n= n0+n1+n2,两个公式结合下就得n= 2*n0+n1-1,在完全二叉树里只有一个树枝的节点只可能是0个或者1个,由此得到n0=(n+1)/2或n0=n/2,合并成一个公式:n0=?(n+1)/2...代入计算看看