Skip to content

1367. Linked List in Binary Tree 👍

  • Time: $O(n \cdot \min(|\texttt{head}|, h))$
  • Space: $O(\min(|\texttt{head}|, h))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  bool isSubPath(ListNode* head, TreeNode* root) {
    if (root == nullptr)
      return false;
    return isContinuousSubPath(head, root) || isSubPath(head, root->left) ||
           isSubPath(head, root->right);
  }

 private:
  bool isContinuousSubPath(ListNode* head, TreeNode* root) {
    if (head == nullptr)
      return true;
    if (root == nullptr)
      return false;
    return head->val == root->val &&
           (isContinuousSubPath(head->next, root->left) ||
            isContinuousSubPath(head->next, root->right));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public boolean isSubPath(ListNode head, TreeNode root) {
    if (root == null)
      return false;
    return isContinuousSubPath(head, root) || isSubPath(head, root.left) ||
        isSubPath(head, root.right);
  }

  private boolean isContinuousSubPath(ListNode head, TreeNode root) {
    if (head == null)
      return true;
    if (root == null)
      return false;
    return head.val == root.val &&
        (isContinuousSubPath(head.next, root.left) || isContinuousSubPath(head.next, root.right));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def isSubPath(self, head: ListNode | None, root: TreeNode | None) -> bool:
    if not root:
      return False
    return (self._isContinuousSubPath(head, root) or
            self.isSubPath(head, root.left) or
            self.isSubPath(head, root.right))

  def _isContinuousSubPath(
      self,
      head: ListNode | None,
      root: TreeNode | None,
  ) -> bool:
    if not head:
      return True
    if not root:
      return False
    return (head.val == root.val and
            (self._isContinuousSubPath(head.next, root.left) or
             self._isContinuousSubPath(head.next, root.right)))