It's follow up problem forBinary Tree Longest Consecutive Sequence II

Given ak-ary tree, find the length of the longest consecutive sequence path.
The path could be start and end at any node in the tree

Have you met this question in a real interview?

Yes

Example

An example of test data: k-ary tree5<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

/**
 * Definition for a multi tree node.
 * struct MultiTreeNode {
 *     int val;
 *     vector<TreeNode*> children;
 *     MultiTreeNode(int x) : val(x) {}
 * };
 */

 class ResultType {
     public:
     int max_len, max_down, max_up;
     ResultType(int len, int down, int up) : max_len(len), max_down(down), max_up(up) {};
 };

class Solution {
public:
    /**
     * @param root the root of k-ary tree
     * @return the length of the longest consecutive sequence path
     */
    int longestConsecutive3(MultiTreeNode* root) {
        // Write your code here
        return helper(root).max_len;
    }

    ResultType helper(const MultiTreeNode* root) {
        if (root == nullptr)
            return ResultType(0, 0, 0);

        int down = 0, up = 0, max_len = 0;
        for (const MultiTreeNode* node : root->children) {
            ResultType tmp = helper(node);
            if (node != nullptr && node->val + 1 == root->val)
                down = max(down, tmp.max_down + 1);
            if (node != nullptr && node->val - 1 == root->val)
                up = max(up, tmp.max_up + 1);
            max_len = max(max_len, tmp.max_len);
        }

        max_len = max(max_len, down + up + 1);
        return ResultType(max_len, down, up);
    }
};