0
\$\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
    \$\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\$ – Graipher Aug 3 '18 at 17:43
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\$
  • \$\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\$ – loremIpsum1771 Aug 7 '18 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.