C++ solution with explanation


  • 0
    N
    class Solution {
    public:
        int longestConsecutive(TreeNode* root) {
            int maxlen = 0;
            if(!root)   return 0;
            find_path(root,maxlen);
            return maxlen;
        }
        
        pair<int,int> find_path(TreeNode* root, int& maxlen){ 
            // find the longest increasing and decreasing consecutive paths length from root
            // return in form [longest increasing path , longest decreasing path]
            /* e.g.       3    ==> root
                        /   \
                       2     1             [3 , 3-2-0] ==> return [1,3]
                      /
                     0
            */
            pair<int,int> ans = make_pair(1,1); //this is the final answer if there is no left and right child
            
            if(root->left){ //left child exists
                pair<int,int> left_ans = find_path(root->left, maxlen);
                if(root->left->val == root->val+1) //increasing path
                    ans.first = 1+left_ans.first;
                else if(root->left->val == root->val-1) //decreasing path
                    ans.second = 1+left_ans.second;
            }
            
            if(root->right){ //right child exists
                pair<int,int> right_ans = find_path(root->right, maxlen);
                if(root->right->val == root->val+1) //increasing path
                    ans.first = max(ans.first , 1+right_ans.first);
                else if(root->right->val == root->val-1) //decreasing path
                    ans.second = max(ans.second, 1+right_ans.second);
            }
            
            maxlen = max(maxlen , ans.first + ans.second - 1); //update maxlen for each Node
            return ans;
        }
    };
    

Log in to reply
 

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