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.
1#include <cstddef>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode(int x) : val(x), next(nullptr) {}
7};
8
9struct TreeNode {
10 int val;
11 TreeNode *left;
12 TreeNode *right;
13 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14};
15
16class Solution {
17public:
18 bool isSubPath(ListNode* head, TreeNode* root) {
19 if (!root) return false;
20 return dfs(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
21 }
22
23 bool dfs(ListNode* head, TreeNode* root) {
24 if (!head) return true;
25 if (!root) return false;
26 if (head->val != root->val) return false;
27 return dfs(head->next, root->left) || dfs(head->next, root->right);
28 }
29};In the C++ implementation, the Solution class contains the method isSubPath, which performs a DFS whenever a node in the tree matches the head of the list. The recursive dfs method checks the linked list path in either child node.
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
Using an explicit stack to simulate recursion, this C solution handles the depth-first search iteratively. Each stack element consists of a tree node and the matching list node associated with that state. We continuously pop from the stack, testing elements.