在一个用数组表示的完全二叉树中，根结点下标为1，下标17和19结点的最近公共祖先下标是（ ）。

A. 1 B. 2 C. 4 D. 8

[tag_link]

correct answer: C

结论

17的祖先为8、4、2、1，19的祖先为9、4、2、1，最近公共祖先下标为4。

推导

17的祖先为8、4、2、1，19的祖先为9、4、2、1，最近公共祖先下标为4。

易错点

父下标为⌊i/2⌋（根下标1）。