[549. Binary Tree Longest Consecutive Sequence II] C++_AC_DFS_with brief explanation


  • 1

    For each node, we have two choices: go left or go right, and the value might be increase or decrease. So, we use pair<int,int> p to store the information: p.first stores the consecutive number of decreasing nodes from this root, p.second stores the consecutive number of increasing nodes from this root. Then we will apply DFS for left child and right child of this root.

    Let's consider the base case: if we reach the leaf node, then the DFS function will return {1,1}, this means that we only have 1 node from this leaf if it is increasing sequence, and we only have 1 node from this leaf if it is decreasing sequence. Now, our max length is 1 + 1 - 1 = 1.(decreasing + increasing - 1)
    Let's look at the following code:

        pair<int,int> l(0,0);
        pair<int,int> r(0,0);
        if(root->left){
            l = dfs(root->left, {1,1});
    

    We apply DFS to the left child of this root, and get the result l.

            if(root->left->val + 1 == root->val){
                cur.first += l.first;
            }
    

    if left child value is 1 less than root->val, then we can see that this child can be a decreasing consecutive node from this root, so we can add the number of decreasing node of this child to our root result.

            if(root->left->val - 1 == root->val){
                cur.second += l.second;
            }
        }
    

    It is the same for the increasing part.

        if(root->right){
            r = dfs(root->right, {1,1});
            if(root->right->val + 1 == root->val){
                cur.first = max(cur.first, r.first + 1);
            }
            if(root->right->val - 1 == root->val){
                cur.second = max(cur.second, r.second + 1);
            }
        }
    

    Similar method for the right child of this root, however, we should notice: cur.first = max(cur.first, r.first + 1);, why? Because we can only choose one path from left and right paths when both of them are all eligible as the decreasing sequence or increasing sequence. So we will choose the largest one as our result.

    So each time when we finish our recursive, we update our final result maxVal.

    Comprehensive code:

    class Solution {
    public:
    int maxVal = 0;
    int longestConsecutive(TreeNode* root) {
        if(root == nullptr) return 0;
        dfs(root, {1,1});
        return maxVal;
    }
    
    pair<int,int> dfs(TreeNode* root, pair<int, int> cur){
        pair<int,int> l(0,0);
        pair<int,int> r(0,0);
        if(root->left){
            l = dfs(root->left, {1,1});
            if(root->left->val + 1 == root->val){
                cur.first += l.first;
            }
            if(root->left->val - 1 == root->val){
                cur.second += l.second;
            }
        }
        if(root->right){
            r = dfs(root->right, {1,1});
            if(root->right->val + 1 == root->val){
                cur.first = max(cur.first, r.first + 1);
            }
            if(root->right->val - 1 == root->val){
                cur.second = max(cur.second, r.second + 1);
            }
        }
        maxVal = max(maxVal, cur.first + cur.second - 1);
        return cur;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.