[LintCode] 619 Binary Tree Longest Consecutive Sequence III 二叉树最长连续序列 III

2021年09月15日 阅读数：2

Given a k-ary tree, find the length of the longest consecutive sequence path.html

The path could be start and end at any node in the tree

Example
An example of test data: k-ary tree 5<6<7<>,5<>,8<>>,4<3<>,5<>,3<>>>, denote the following structure:
5
/   \
6     4
/|\   /|\
7 5 8 3 5 3
Return 5, // 3-4-5-6-7
java

Java:node

``` class ResultType {
int globalMax;
int maxUp;
int maxDown;
public ResultType(int globalMax, int maxUp, int maxDown) {
this.globalMax = globalMax;
this.maxUp = maxUp;
this.maxDown = maxDown;
}
}

public int longestConsecutive3(MultiTreeNode root) {
return helper(root).globalMax;
}

public ResultType helper(MultiTreeNode root) {

if (root == null) {
return new ResultType(0, 0, 0);
}

int maxUp = 0;
int maxDown = 0;
int max = Integer.MIN_VALUE;

for (MultiTreeNode child : root.children) {

if (child == null) {
continue;
}

ResultType childResult = helper(child);
if (child.val + 1 == root.val) {
maxDown = Math.max(maxDown, childResult.maxDown + 1);
}

if (child.val - 1 == root.val) {
maxUp = Math.max(maxUp, childResult.maxUp + 1);
}

max = Math.max(Math.max(max, childResult.globalMax), maxUp + maxDown + 1);
}

return new ResultType(max, maxUp, maxDown);
}
```