1
\$\begingroup\$

I written code to solve this problem which I found on leetcode. My solution worked for the vast majority of the test cases run against it but failed on 2 for some reason. The first test case it failed on had a extremely large input size for the tree so it's really hard to determine what is actually wrong with the algorithm I wrote: 

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

def lcs(root):
    if root is None:
        return 0
    left_lcs = lcs(root.left)
    right_lcs = lcs(root.right)
    add_to_left = 0
    add_to_right = 0
    if root.left is not None:
        if root.left.val - root.val == 1:
            add_to_left = 1
    if root.right is not None:
        if root.right.val - root.val  ==1:
            add_to_right =1 
    if root.right is None and root.left is None:
        return 1
    return max(add_to_left + left_lcs, add_to_right + right_lcs)

Are there any glaring issues with the code that I'm just missing?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ If the longest consecutive sequence is longer than the stack size (1000 by default), this will raise an exception. So in Python you might want to use an iterative approach instead of a recursive one. \$\endgroup\$ Commented Aug 3, 2018 at 17:43

1 Answer 1

Reset to default
2
\$\begingroup\$

Recursion is probably your main problem, as Graipher mentioned in the comments.

You could refactor it to be iterative:

def lcs(root):
    if root is None:
        return 0
    longest_sequence = 0
    nodes = dict()
    nodes[root] = 1
    while True:
        new_nodes = dict()
        for node, length in nodes.items():
            for subnode in (node.left, node.right):
                if subnode:
                    if subnode.val - node.val == 1:
                        new_nodes[subnode] = length + 1
                    else:
                        new_nodes[subnode] = 1
            longest_sequence = max(longest_sequence, length)
        nodes = new_nodes
        if not nodes:
            break
    return longest_sequence
\$\endgroup\$
1
  • \$\begingroup\$ Ok, so you're essentially just doing a level order traversal instead of a depth first recursive solution. Do you think it would be better to just do recursive solutions in another language? Using recursive dfs was just more intuitive to me in this case. \$\endgroup\$ Commented Aug 7, 2018 at 14:39

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.