瓶盖换酒问题

二叉树问题无处不在，在微信群里面遇到这样有趣的问题：2元钱可以买一瓶瓶酒，一瓶啤酒喝完可以得到1个空瓶和1个瓶盖，4个瓶盖能换一瓶酒，2个空瓶可换一瓶酒，那么问题来了，10元最多可以喝到几瓶瓶酒？

换酒问题

看似简单的问题，你的答案又是多少呢？

接下来我们来分析一下这个问题：

首先，10元不管你怎么换，什么时候换，都是得到最原始的5瓶酒，也就5个空瓶（A）和5个瓶盖（B），即5A5B；

其次，我们简化下交换过程，2个空瓶换一瓶酒也就是得到1空瓶和1瓶盖，本质上就是-1A和+1B操作（简称向左走）；4个瓶盖换一瓶酒本质上就是+1A和-3B操作（向右走）。

然后，我们看到，每次换酒无非就是向左走向右走的选择，而且都能多喝了一瓶酒，也就是说，交换次数越多次，喝到的酒越多。

要知道最多能喝多少瓶酒，实际上只要求出最大的交换次数，这个可以通过遍历二叉树取得，这里我们使用先序遍历。

这里我们用java实现算法，新建一个类BinTreeTraverse和内部类Node子节点，根据二叉树的结构每个父节点都保留左右两个子节点，还有交换次数，空瓶子数和瓶盖数，track是交换记录，A表示2个空瓶换一瓶，B表示4个瓶盖换一瓶酒；

子节点

然后我们要进行的是生成这个二叉树关系，通过判断左右节点是否存在，然后递归调用就可以生成关系二叉树，每次生成节点都把最大交换次数和最大交换次数存起来。

二叉树关系生成

最后执行完成我们打印记录的maxNode的最大值和track：

maxTime = 10；

track = AAAABABABA；

我们可以知道，最多可以交换10次，加上原来的5瓶酒，最多可以喝到15瓶酒。

其实我们在creatTree()函数中打印出所有交换次数等于10的结果，你会发现其实又156种喝到15瓶酒的方法。