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
class Solution:
  def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> 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: Optional[ListNode], root: Optional[TreeNode]) -> 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))