619.二叉树的最长连续子序列III

描述

这题是 二叉树的最长连续子序列II 的后续。
给出一棵 k叉树，找到最长连续序列路径的长度.
路径的开头跟结尾可以是树的任意节点。

样例

一个样例如下：k叉树 5<6<7<>,5<>,8<>>,4<3<>,5<>,3<>>>，表示如下结构:

         5
       /   \
      6     4
     /|\   /|\
    7 5 8 3 5 3

返回 5, // 3-4-5-6

分析

和II之间区别只是由二叉变成了多叉，所以用for循环多个子结点即可。

代码

多叉树的代码可以更清晰展现思路

/**
 * Definition for a multi tree node.
 * public class MultiTreeNode {
 *     int val;
 *     List<TreeNode> children;
 *     MultiTreeNode(int x) { val = x; }
 * }
 */
class ResultType {
    int max_length;
    int max_up;
    int max_down;
    public ResultType(int length, int up, int down) {
        this.max_length = length;
        this.max_up = up;
        this.max_down = down;
    }
}
    
public class Solution {
    /**
     * @param root the root of k-ary tree
     * @return the length of the longest consecutive sequence path
     */
    public int longestConsecutive3(MultiTreeNode root) {
        return helper(root).max_length;
    }
    
    private ResultType helper(MultiTreeNode root) {
        if (root == null) {
            return new ResultType(0, 0, 0);
        }
        
        int up = 0;
        int down = 0;
        int max_length = 1;
        for (MultiTreeNode node : root.children) {
            ResultType type = helper(node);
            if (node.val - 1 == root.val) {
                up = Math.max(up, type.max_up + 1);
            }
            if (node.val + 1 == root.val) {
                down = Math.max(down, type.max_down + 1);
            }
            // 将当前结点的max_length更新为子结点的max_length的最大值
            max_length = Math.max(max_length, type.max_length);
        }
        
        // 计算可以转弯的max_length,比较找出最大值
        int length = down + 1 + up;
        length = Math.max(length, max_length);
        return new ResultType(length, up, down);
    }
}