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?