DFS C++, Python solutions


  • 8
    Z

    c++ solution:

    class Solution {
    public:
        int longestConsecutive(TreeNode* root) {
            int longest = 0;
            dfs(root, root, longest);
            return longest;
        }
    
        pair<int, int> dfs(TreeNode * node, TreeNode * parent, int & longest) {
            if ( NULL == node ) {
                return make_pair(0, 0);
            }
            auto left = dfs(node->left, node, longest);
            auto right = dfs(node->right, node, longest);
            longest = max(longest, left.first + right.second + 1);
            longest = max(longest, left.second + right.first + 1);
            int inc = 0, dec = 0;
            if ( node->val == parent->val + 1 ) {
                inc = max(left.first, right.first) + 1;
            }
            if ( node->val == parent->val - 1 ) {
                dec = max(left.second, right.second) + 1;
            }
            return make_pair(inc, dec);
        }
    };
    

    python solution

    class Solution(object):
        def longestConsecutive(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def dfs(node, parent):
                if not node:
                    return 0, 0
                li, ld = dfs(node.left, node)
                ri, rd = dfs(node.right, node)
                l[0] = max(l[0], li + rd + 1, ld + ri + 1)
                if node.val == parent.val + 1:
                    return max(li, ri) + 1, 0
                if node.val == parent.val - 1:
                    return 0, max(ld, rd) + 1
                return 0, 0
            l = [0]
            dfs(root, root)
            return l[0]
    

  • 0
    L

    Why'd you use a list when you're just storing one number (python solution)?


  • 0
    Z

    @livelearn said in DFS C++, Python solutions:

    Why'd you use a list when you're just storing one number (python solution)?

    It's just a trick, because I need to modify it in inner scope.


  • 0
    L

    @zqfan Can't use a global variable or something? I feel like there must be another way other than creating a list.


  • 0
    Z

    @livelearn said in DFS C++, Python solutions:

    @zqfan Can't use a global variable or something? I feel like there must be another way other than creating a list.

    of course you can use global variables, or if you are using py3, you can use nonlocal keyword instead of global variables.


Log in to reply
 

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