比较好玩的 Binary Tree 概率题

给一个node有parent指针的 complete tree，每个node的值为 0 / 1；每个parent的值为两个子node的 “AND” 结果；现在把一个leaf翻牌子（0变1或者1变0）

1，写代码 (太简单了不贴了。。)

2, 时间复杂度的期望值是多少？(一颗赛艇)

leaf node 区分左右的话，可能有4种组合，每种组合分别有 flip{left, right} 两种选择，于是：

• 0,0 - 左，变成1； 右，变成1

• 0,1 - 左，不变； 右，变成0

• 1,0 - 左，变成0；右，不变；

• 1,1 - 左，不变，右，不变；

总共会造成 parent node 的值和之前有变化的可能是 4 种，所以在每一层 parent - child 的关系中任意 flip 一个 child，有 1/2 的几率造成 parent 的值也被 flip.

假设二叉树中总共有 N 的节点，其深度/自底向上路径长是 h = O(logN)，那我们自底向上的更新路径实际次数就会在 【1, h】 的闭区间内，最少更新次数为 1 (计算了 leaf，但是发现对 parent 无任何影响)，最大计算次数为 h ，代表一路更新到了 root.

那我们总共会计算【1,2,3 ... h】层的概率就是 【1 , 1/2 , (1/2)^2 , (1/2)^3 ... (1/2)^h】，其对应的计算次数期望值就是 1 + 1 1/2 + 2 (1/2)^2 + 3 (1/2)^3 + .... h (1/2)^h = 1 + Sigma (h / 2^h)，在 n 趋近于无限的情况下，upper bound 是 1 + 2 = 3 ~ 所以总共的计算次数期望值确实是常数。