20-line C++ DFS Solution


  • 1
    class Solution {
    public:
        int res;
        int longestConsecutive(TreeNode* root) {
            if(root) 
                DFS(root);
            return res;
        }
        pair<int, int> DFS(TreeNode *node)
        {
            pair<int, int> leftRes, rightRes;
            if(node->left)
                leftRes = DFS(node->left);
            if(node->right)
                rightRes = DFS(node->right);
            int inc = 1, des = 1;
            if(node->left && node->val == node->left->val + 1)
                inc = max(inc, 1 + leftRes.first);
            if(node->right && node->val == node->right->val + 1)
                inc = max(inc, 1 + rightRes.first);
            if(node->left && node->val == node->left->val - 1)
                des = max(des, 1 + leftRes.second);
            if(node->right && node->val == node->right->val - 1)
                des = max(des, 1 + rightRes.second);
            res = max(res, inc + des - 1);
            return pair<int, int>(inc, des);
        }
    };
    

Log in to reply
 

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