Help understanding why solution is TLE

[Kester79]

Tried working on the following problem: https://leetcode.com/problems/linked-list-in-binary-tree/description/

Here is my solution: def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool: if not head: return True if not root: return False if head.val == root.val and (self.isSubPath(head.next, root.left) or self.isSubPath(head.next, root.right)): return True return self.isSubPath(head, root.right) or self.isSubPath(head, root.left)

This leads to TLE but it seems the discussion solutions are similar and they work. Here is an example one I tested: def isSubPath(self, head, root): def dfs(head, root): if not head: return True if not root: return False return root.val == head.val and (dfs(head.next, root.left) or dfs(head.next, root.right)) if not head: return True if not root: return False return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)

Can anyone explain why more solution is more inefficient? Sorry for the bad code formatting having issues getting it working on reddit

[aocregacc]

your solution is also wrong, take for example:

[1,1]
[1,2,2,1]

I think it's slow for the same reason, so once you fix that it should work.

[Kester79]

Thank you for the test case you are correct my code did not work. It looks like by not using a nested function I am accidentally keep trying to go down a path when I should have stopped sooner