Sponsored
Sponsored
This approach utilizes depth-first search (DFS) recursively to search through the binary tree. For each node that matches the head of the linked list, we will try to match the remaining nodes of the linked list with the children nodes of the current tree node.
Time Complexity: O(n * m), where n is the number of tree nodes and m is the number of list nodes. Space Complexity: O(h), where h is the height of the tree, due to recursion stack usage.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class TreeNode:
7 def __init__(self, val=0, left=None, right=None):
8 self.val = val
9 self.left = left
10 self.right = right
11
12class Solution:
13 def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
14 if not root:
15 return False
16 return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
17
18 def dfs(self, head: ListNode, root: TreeNode) -> bool:
19 if not head:
20 return True
21 if not root:
22 return False
23 if head.val != root.val:
24 return False
25 return self.dfs(head.next, root.left) or self.dfs(head.next, root.right)The Python version of the solution uses recursive DFS. The function isSubPath determines starting points for matching the linked list's path in the tree using the helper method dfs.
This strategy employs an iterative depth-first search using an explicit stack to avoid recursion-driven call stacks. We simulate the recursive call stack with a custom stack structure, effectively managing process states iteratively as we check for potential subpaths.
Time Complexity: O(n * m), Space Complexity: O(n), where n is the number of nodes in the tree and m is the list node count due to stack usage.
1
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; next = null; }
}
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public bool IsSubPath(ListNode head, TreeNode root) {
var stack = new Stack<(TreeNode, ListNode)>();
stack.Push((root, head));
while (stack.Count > 0) {
var (treeNode, listNode) = stack.Pop();
if (listNode == null) return true;
if (treeNode == null) continue;
if (treeNode.val == listNode.val) {
stack.Push((treeNode.left, listNode.next));
stack.Push((treeNode.right, listNode.next));
}
if (listNode.next != null) {
stack.Push((treeNode.left, listNode));
stack.Push((treeNode.right, listNode));
}
}
return false;
}
}For C#, the iterative DFS utilizes a stack for examination of the tree nodes in combination with the linked list nodes. Here, Tuple-like stack entries facilitate organized, orderly management of pairings.