Problem

Given a binary tree root and a linked list with head as the first node.

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

https://leetcode.cn/problems/linked-list-in-binary-tree/

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.

Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

  • The number of nodes in the tree will be in the range [1, 2500].
  • The number of nodes in the list will be in the range [1, 100].
  • 1 <= Node.val <= 100 for each node in the linked list and binary tree.

Test Cases

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import pytest

import os
import sys
sys.path.append(os.path.dirname(os.path.dirname(__file__)))
from _utils.binary_tree import build_tree
from _utils.linked_list import build_linked_list
from solution import Solution

null = None


@pytest.mark.parametrize('head, root, expected', [
([4,2,8], [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3], True),
([1,4,2,6], [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3], True),
([1,4,2,6,8], [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3], False),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, head, root, expected):
assert sol.isSubPath(build_linked_list(head), build_tree(root)) == expected

Thoughts

按某个顺序遍历二叉树,如前序遍历(pre-order,NLR)。对于当前节点,判断是否存在以其为起点的与给定链表一致的路径。

时间复杂度 O(n * 2ᵐ) ≤ O(n²),其中 n 是二叉树的节点数量,m 是链表的节点数量。遍历整棵树的时间是 O(n),对于其中每个节点,以其为起点跟链表比较的最坏时间复杂度是 O(2ᵐ) ≤ O(n),这是高度为 m 的二叉树的叶子节点的量级。

不知道能否像 KMP 算法或者 AC 自动机(3213. Construct String with Minimum Cost 中用到)那样,以 O(n + m) 时间完成呢。本题跟 AC 自动机的场景是相反的,AC 自动机相当于在链表中找二叉树的每一条路径,而本题是在二叉树的每一条路径中找链表。

Code

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from typing import Optional


# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSubPath(self, head: Optional['ListNode'], root: Optional['TreeNode']) -> bool:
def match(head: 'ListNode', root: 'TreeNode') -> bool:
if head is None: return True
if root is None or root.val != head.val: return False
return match(head.next, root.left) or match(head.next, root.right)

stack = []
while root or stack:
if root:
if match(head, root): return True
stack.append(root)
root = root.left
else:
root = stack.pop().right

return False