Passing variable by reference in python

Question

I am practicing a leetcode question and I am having trouble updating my variable. I think I am not passing my reference correctly. I am expecting the answer to be 3 but I am getting 1. I ran through the code and the answer 3 is achieved but when i jump back out of my recursion I am getting 1.

The goal is the find the longest consecutive chain of nodes in a binary tree.

ex:

Answer would be 3 --> 3,4,5

Below is the runnable code:

class Node(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def DFS(self, root):
        count = 0
        if root:
            count += 1
            q = [root]
            while q:
                n = q.pop()
                T = 0
                if n.left:
                    if n.left.val == n.val + 1:
                        q.append(n.left)
                        T = 1
                if n.right:
                    if n.right.val == n.val + 1:
                        q.append(n.right)
                        T = 1
                if T:
                    count += 1
        return count

    def longestConsecutive(self, root, count=0):
        """
        :type root: TreeNode
        :rtype: int
        """
        c = count
        if root:
            c = max(c, self.DFS(root))
            self.longestConsecutive(root.left, c)
            self.longestConsecutive(root.right, c)
        return c

a = Node(1)
b = Node(3)
c = Node(2)
d = Node(4)
e = Node(5)

a.right = b
b.left = c; b.right = d
d.right = e

poop = Solution()
print(poop.longestConsecutive(a))

You will get better and faster answers if you produce a minimal example of the problem, without all the unrelated logic around it. If you're unsure about your DFS implementation, post that as a separate question — salezica
– salezica, Commented May 10, 2017 at 20:26
You can't pass variables by reference in Python. In fact, you never pass variables around at all; you can only pass objects. — user2357112
– user2357112, Commented May 10, 2017 at 20:28
Technically, Python does not support pass-by-reference semantics. — juanpa.arrivillaga
– juanpa.arrivillaga, Commented May 10, 2017 at 20:29
You're using T, an int variable, as a boolean flag. Just use True and False. — Arya McCarthy
– Arya McCarthy, Commented May 10, 2017 at 20:29

Nikolas Stevenson-Molnar · Accepted Answer · 2017-05-10 20:33:34Z

3

You're returning count from the longestConsecutive method but not assigning it to anything. Try this instead:

def longestConsecutive(self, root, count=0):
    """
    :type root: TreeNode
    :rtype: int
    """
    c = count
    if root:
        c = max(c, self.DFS(root))
        c = self.longestConsecutive(root.left, c)
        c = self.longestConsecutive(root.right, c)
    return c

answered May 10, 2017 at 20:33

Nikolas Stevenson-Molnar

4,7502 gold badges25 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Chris · Accepted Answer · 2017-05-10 20:38:14Z

2

Your problem is the the value of c is not saved. While inside of your recursive calls, the value of c is correctly set to 3. But when control flow begins to move back up the recursive stack, the value of c is lost. To fix this, you can make c an attribute of Solutions. That way, the value of c can be saved through out your recursive calls.

def longestConsecutive(self, root, count=0):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.c = count # make c an attribute of Solution.
        if root:
            self.c = max(self.c, self.DFS(root))
            self.longestConsecutive(root.left, self.c)
            self.longestConsecutive(root.right, self.c)
        return self.c

Which has the output:

edited May 10, 2017 at 20:38

answered May 10, 2017 at 20:32

Chris

23.2k8 gold badges63 silver badges91 bronze badges

Collectives™ on Stack Overflow

Passing variable by reference in python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related