描述
这题是 二叉树的最长连续子序列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);
}
}