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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int x) { val = x; next = null; }
5}
6
7public class TreeNode {
8 public int val;
9 public TreeNode left;
10 public TreeNode right;
11 public TreeNode(int x) { val = x; }
12}
13
14public class Solution {
15 public bool IsSubPath(ListNode head, TreeNode root) {
16 if (root == null) return false;
17 return DFS(head, root) || IsSubPath(head, root.left) || IsSubPath(head, root.right);
18 }
19
20 private bool DFS(ListNode head, TreeNode root) {
21 if (head == null) return true;
22 if (root == null) return false;
23 if (head.val != root.val) return false;
24 return DFS(head.next, root.left) || DFS(head.next, root.right);
25 }
26}This C# code consists of the main function IsSubPath and helper DFS function which operates recursively with identical logic as described in previous sections. The methods collaborate to find the subpath.
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
Java implements iterative DFS with a stack approach, leveraging the Pair class to store tree and list node relationships. This facilitates stack-driven traversal, exploring nodes iteratively for list path matching.