算法-二叉树-多叉树中最长的连续序列.md

二叉树：https://cheonhyangzhang.gitbooks.io/leetcode-solutions/content/solutions-501-550/549-binary-tree-longest-consecutive-sequence-ii.html

多叉树：https://gist.github.com/thanlau/34bd056dd0b1662d5fd483e157a27dfb

/**
 * Definition for a multi tree node.
 * public class MultiTreeNode {
 *     int val;
 *     List<MultiTreeNode> children;
 *     MultiTreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param root the root of k-ary tree
     * @return the length of the longest consecutive sequence path
     */
     int max = 0;

    public int longestConsecutive3(MultiTreeNode root) {
        // Write your code here
        if (root == null){
            return 0;
        }
        helper(root);
        return max;
    }

    public int[] helper(MultiTreeNode root) {
        int up = 0;
        int down = 0;
        if (root == null){
            return new int[]{down, up};
        }
        for ( MultiTreeNode node : root.children ){
            int[] h = helper(node);
            if (node.val == root.val + 1){
                down = Math.max(down, h[0] + 1);
            }
            if (node.val + 1 == root.val){
                up = Math.max(up, h[1] + 1);
            }
        }
        max = Math.max(max, down + up + 1);
        return new int[]{down, up};
    }
}