某地主担心农民偷取他的粮食,雇人挖了大量地窖来屯粮,这些地窖层层排列,只有一个总入口。 每个地窖都有一个随机且唯一的数字编号(1 ... N)。聪明的农夫经过一番侦察,发现所有的地窖形成了一颗满二叉树,只有叶子节点中才存放有粮食,粮食数量与地窖编号相同。 狡猾的地主设置了报警装置,只要任意两个相邻的叶子节点中粮食被偷,就会自动报警。
农夫事先并不知道地窖分布图,但是他无意间得到了地窖组成的二叉树的前序遍历和中序遍历结果,请帮忙计算一下,在不触发报警装置的情况下,农夫最多可以偷取地主多少粮食。
提示:
- 如果一个二叉树的层数为K,且节点总数是2k -1 ,则它就是满二叉树,如下图所示。
- 下图中节点1和节点2,节点2和节点3均为相邻的叶子节点, 节点1和节点3不属于相邻叶子节点;