已知一棵二叉树按顺序存储的一维稀疏数组表示：

其后序遍历序列为（ ）。

A. ghbefhca B. gbdehcfa C. gdbhefca D. bgdehcfa

[tag_link]

correct answer: C

结论

C，后序为gdbhefca。

推导

索引0:a、1:b、2:c、4:d、5:e、6:f、9:g、12:h；左子树后序g,d,b，右子树后序h,e,f,c，最后根a，合并为gdbhefca。

易错点

把空槽当作结点。