http://www.lintcode.com/en/problem/binary-tree-longest-consecutive-sequence-iii/

this is a n-nary tree where devide and conquer can also be done. just put down the job into a loop. while keeping the maxLen of a single sub branch. once jump out of the loop, compare that single with the left + right + 1 to get the max for the entire tree

public class Solution {
    /**
     * @param root the root of k-ary tree
     * @return the length of the longest consecutive sequence path
     */
    class ReturnType {
        int maxLen;
        int maxUp;
        int maxDown;
        public ReturnType(int maxLen, int maxUp, int maxDown) {
            this.maxLen = maxLen;
            this.maxUp = maxUp;
            this.maxDown = maxDown;
        }
    }
    public int longestConsecutive3(MultiTreeNode root) {
        // Write your code here
        if (root == null) {
            return 0;
        }

        ReturnType ans = helper(root);
        return ans.maxLen;
    }

    public ReturnType helper(MultiTreeNode root) {
        if (root == null) {
            return new ReturnType(0, 0, 0);
        }

        int up = 0; 
        int down = 0;
        int max = 1;
        for (int i = 0; i < root.children.size(); i++) {
            ReturnType cur = helper(root.children.get(i));
            if (root.val == root.children.get(i).val + 1) {
                down = Math.max(down, cur.maxDown + 1);
            }

            if (root.val == root.children.get(i).val - 1) {
                up = Math.max(up, cur.maxUp + 1);
            }

            max = Math.max(cur.maxLen, max);
        }

        max = Math.max(max, up + down + 1);
        return new ReturnType(max, up, down);
    }