# 比较好玩的 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 \~ 所以总共的计算次数期望值确实是常数。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/binary_tree/bi_jiao_hao_wan_de_binary_tree_gai_lv_ti.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.