寻找二叉树最优路径

 

一个用数组表示的二叉树int[] tree=new int[]{7,5,46,1,8,9,36...};，根节点为7,下面俩子节点分别是5和46，以此类推产生其他子节点。现在需要找出该二叉树所有节点之和最大的路径。

 

首先想到的是将该数组变成一个树形结构的数据再遍历该树节点值相加，得到最后结果最大的叶子节点，再回溯到根节点得到路径，但这样耗费太多空间资源。每个节点需要存储其本身的值，然后还有存储其子节点和父节点。事实上我们只是路径而已，不需要存储节点间的关系，所以，我们可以新建一个可以存放2的n次方个整数的数组用以存储路径，使用整数来存储所有的路径，因为在计算机中的数据都是使用二进制表示，010101，我们就可以利用这样的特性构造一条路径，定义1为右节点，0为左节点。例如：101即是在第一个节点右转，下一个节点左转，再下个节点右转。应用到上面的例子中就是从7开始到46,再到9...光知道可以使用这样的结果作为路径存储还不够。还要知道怎么用它。这里我使用左遍历来遍历二叉树。以上面的例子来展示就是从7到5到1再回溯到5查看5的有节点，就是8，再回溯到5就没有其他节点了，回溯到7，处理有节点的46再到46的左子节点9。这样的遍历原则可以让路径的生产规则如同数字的自增规则，一开始的时候路径的表示是000（以上面的例子做示范，假设不包括根节点共有三个层次的节点），000（0）即是所有的拐点都是左。而下一条路径刚好是回溯一个节点，即最后一个拐点指向右，即001（1），再下一个节点则是回溯两个节点，中间的指向右，最后一个拐点指向左。即010（2），路径就这样0,1,2,3...递增下去。

 

按照最顶上的例子，我们得到4个路径00,01,10,11。对应的值分别是7+5+1=13，7+5+8=20，7+46+9=62，7+46+36=89。最终放在一个存放结果的数组里（实际上只需要一个存储结果的数组就可以了，路径是递增的，即是数组元素的下标）。new int[]{13,20,62,89}。最大的路径就是11(3)。

 

在检查路径时需要知道树的层次有多深，再用位移去逐个check每一位上的值就可以知道左还是右节点了。