Given a binary 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

    1
   / \
  2   0
 /
3

Return4//0-1-2-3

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

 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 binary tree
     * @return the length of the longest consecutive sequence path
     */
    int longestConsecutive2(TreeNode* root) {
        // Write your code here
        return helper(root).max_len;
    }

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

        ResultType left = helper(root->left);
        ResultType right = helper(root->right);

        int down = 0, up = 0;
        if (root->left && root->left->val + 1 == root->val)
            down = left.max_down + 1;
        if (root->left && root->left->val - 1 == root->val)
            up = left.max_up + 1;

        if (root->right && root->right->val + 1 == root->val)
            down = max(down, right.max_down + 1);
        if (root->right && root->right->val - 1 == root->val)
            up = max(up, right.max_up + 1);

        int max_len = down + up + 1;
        if (left.max_len > max_len)
            max_len = left.max_len;
        if (right.max_len > max_len)
            max_len = right.max_len;

        return ResultType(max_len, down, up);
    }
};