算法题：树形数组中，最长路径怎么求？

这道题是一道求树形数组的最长路径。其实本篇是一个欠账。1年前，我遇到了这道题。当时看到题的第一瞬间，就知道应该采用递归的思想，可手实在是太生了。平时的工作更多是设立目标、路径规划、框架设计、模块划分、紧急处置、review代码。即使是直接动手修改，也更多是局部性修改完善，基本就没有机会从0开始写代码。所以导致的结果是，我知道我思路正确、最终能做出来，可总被小地方卡住，没有调试出结果，悲剧了。至此，我就有些念念不忘了，总想找时间把它给做出来，总想看到程序输出那个结果30。前一段时间，我动手重拾代码，就像当年新入职一样，一行行、一步步写代码。这次给弄出来了，心结是解了，也有了新的困惑。不管了，把题和答案贴出来，大家一起玩玩吧。

题目

求一颗树形数组的最长路径，由根节点开始往下走，每次只能选择自己的叶子节点。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30

思路

先分析题目，这是一颗树形数组。要求从根节点开始，遍历节点去求最长路径，所以自然的就想到了递归。既然是递归，那么就需要考虑到三个要素：一是找出终止条件，二是找出返回值，三是明确这一步递归干了什么。咱们每一项都说说。

一、找出终止条件

终止条件其实就是传入的树形数组为空，判断条件是 if(array == null || array.length == 0 || array[0] == null || array[0].length == 0)，此时就应该返回 0。我的个人理解，终止条件就是在某些极端情况下获得了确定值。

二、找出返回值

返回值就是需要确定执行当前递归后需要返回的值。像本题目，就是返回当前传入的树形数组的遍历后的最长路径。这个值往往就是问题的答案值。其实，这也是与终止条件的返回值相呼应。不停的递归计算，不停的压栈，直至满足了终止条件，获得了确定值，就逐层出栈，计算出各个函数的确定值。

三、本步递归的操作

本步的递归操作则可以分为两个部分，一是获得根节点的子树，二是计算出这个根节点出发的最长路径。

获取根节点的子树

这是能够持续递归操作的核心，即 getSubArray函数 所描述的内容。这里面是把当前的树形数组分解成根节点和它的子树数组。这就是递归思想最有意思的地方。

计算最长路径

既然已经将当前的树形数组分解成根节点和它的子树数组，那么最长路径就转化为根节点的值加上它所有子树数组的最长路径的最大值。

写到这里，想起来当年教我数据结构的老师，想起了那段似懂非懂，而又青春飞扬的日子。

答案

TreeArray.java 代码文件内容如下：

import java.util.Scanner;
 
 
public class TreeArray {
 
    public void printArray(int[][] array){
        for (int[] t: array ) {
            String[] strArray = new String[t.length];
            for(int j=0; j< t.length; j++){
                strArray[j] = String.valueOf(t[j]);
            }
            System.out.println(String.join(" ", strArray));
        }
        System.out.println("");
    }
 
    public int[][] getSubArray(int[][] array, int i, int j){
        int tempSize = array.length - i;
        int [][] temp = new int[tempSize][tempSize];
 
        for(int r=0; r<tempSize; r++){
            for(int c=0; c< tempSize; c++){ temp[r][c] = array[i+r][j+c]; } } return temp; } public int getMaxLen(int[][] array){ if(array == null || array.length == 0 || array[0] == null || array[0].length == 0){ return 0; } int root = array[0][0]; int[][] leftArray = getSubArray(array, 1,0); int[][] rightArray = getSubArray(array, 1,1); int leftLen = getMaxLen(leftArray); int rightLen = getMaxLen(rightArray); int len = root; if(leftLen > rightLen){
            len += leftLen;
        }else{
            len += rightLen;
        }
 
        return len;
    }
 
    public static void main(String[] args) {
        TreeArray treeArray = new TreeArray();
 
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数组大小：");
        int arraySize = Integer.parseInt(sc.nextLine());
        System.out.println("arraySize: " + arraySize);
 
        int[][] tree = new int[arraySize][arraySize];
 
        System.out.println("请输入树形数组节点：");
        for (int i=0; i< arraySize; i++){
            String[] value = sc.nextLine().split(" ");
            int j = 0;
            for(String v : value){
                 tree[i][j] = Integer.parseInt(v);
                 j++;
            }
        }
        System.out.println("");
 
        int maxPathlen = treeArray.getMaxLen(tree);
 
        System.out.println("" + maxPathlen);
    }
}