解法

第一问

第一问比较好求，设状态\(f[i]\)为有\(i\)个叶子节点时的期望深度。考虑从上一个状态分裂会多对总深度做\(f[i-1]+2\)的贡献，可以知道：

\[ f[i] = \frac{f[i-1] * (i-1) + f[i-1] + 2}{i} = f[i-1] + \frac{2}{i} \]

第二问

第二问难了很多，重点设状态\(f[i][j]\)：有\(i\)个叶子节点深度大于等于\(j\)的期望树高。考虑枚举一个\(k\)为左子树叶子结点的个数，计算：

\[ f[i][j] = \sum_{k = 1}^{i – 1} f[k][j – 1] + f[i – k][j – 1] – f[k][j – 1] * f[i – k][j – 1] \]

后面删掉重复计算的部分。答案是\(\sum_{i = 1}^{n – 1} f[n][i] \)。