Most of the Solutions Return a Pair While I don't


  • 0
    I
    class Solution {
        int result = 0;
    public:
        // flag == -1 means I don't care about the result it returns
        int dfs(TreeNode* root, int flag) {
            int inc = 0;
            int dec = 0;
            
            if (root->left) {
                if (root->left->val == root->val + 1) {
                    dec = dfs(root->left, 1);
                } else if (root->left->val == root->val - 1) {
                    inc = dfs(root->left, 0);
                } else {
                	// need to traverse the children to see if the longest path is inside the child
                    dfs(root->left, -1);
                }
            }
            
            if (root->right) {
                if (root->right->val == root->val + 1) {
                    dec = max(dec, dfs(root->right, 1));
                } else if (root->right->val == root->val - 1) {
                    inc = max(inc, dfs(root->right, 0));
                } else {
                    dfs(root->right, -1);
                }
            }
            
            // since increasing branch and decreasing branch should be in different branches
            // so we can simply add them together
            result = max(result, inc + dec + 1);
            
            if (flag == -1) return -1;
            return flag ? dec + 1 : inc + 1;
        }
        int longestConsecutive(TreeNode* root) {
            if (!root) return 0;
            dfs(root, -1);
            return result;
        }
    };
    

Log in to reply
 

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