[LeetCode]: 549. Binary Tree Longest Consecutive Sequence II

https://leetcode.com/contest/leetcode-weekly-contest-27/problems/binary-tree-longest-consecutive-sequence-ii/

Solution:
This is an interesting question. Similar to the one asking for the longest path for a binary tree, but this question add another constrain: the longest consecutive sequence. For each treenode, we need to check its left and right child. For the question asking for the longest path, we just need to return the larger one of longest paths from the left and right sub-trees, and the final result will be the maximum of (left + right + 1). But for this question, we need to return two values: one is the larger one of the two possible longest increasing paths from the left and right sub-trees, and the other is the larger one of the two possible longest decreasing paths from the left and right sub-trees. Since when move up to the next level (bottom-up direction), the longest consecutive sequence will be the maximum of (the larger one of the two possible longest increasing paths (could from the left sub-tree or the right sub-tree) + the larger one of the two possible longest decreasing paths (from the opposite side to the sub-tree in the first term)  + 1). See the code below:

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        int res = 0;
        find(root, res);
        return res;
    }
private:
    pair<int, int> find(TreeNode *r, int &res){
        if(!r) return make_pair(0, 0);
        pair<int, int> ra = find(r->left, res), rb = find(r->right, res);
        int a = 1, b = 1;
        if(r->left&&r->left->val+1==r->val) a = max(a, 1 + ra.first);
        if(r->right&&r->right->val+1==r->val) a = max(a, 1 + rb.first);
        if(r->left&&r->left->val-1==r->val) b = max(b, 1 + ra.second);
        if(r->right&&r->right->val-1==r->val) b = max(b, 1 + rb.second);
        res = max(res, a + b - 1);
        return make_pair(a, b);
    }
};