C++ dfs search


  • 0
    T
    class Solution {
    public:
        // update inc if node.val+1 == node.child.val
        // update desc if node.val-1 == node.child.val
        void longest(TreeNode *node, int &inc, int &desc, int &maxv) {
            if (!node) return;
            int inc1 = 0, inc2 = 0, desc1 = 0, desc2 = 0;
            
            if (node->left) {
                longest(node->left, inc1, desc1, maxv);
                if (node->val+1 != node->left->val) inc1 = 0;
                if (node->val-1 != node->left->val) desc1= 0;
            }
            if (node->right) {
                longest(node->right, inc2, desc2,maxv);
                if (node->val+1 != node->right->val) inc2 = 0;
                if (node->val-1 != node->right->val) desc2= 0;
            }
            inc = max(inc1, inc2) + 1, desc = max(desc1, desc2) + 1;
            maxv = max(maxv, max(inc1+desc2, inc2+desc1)+1);
        }
        int longestConsecutive(TreeNode* root) {
            int inc = 0, desc = 0, maxv = 0;
            longest(root, inc, desc, maxv);
            return maxv;
        }
    };
    

Log in to reply
 

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