This problem looks busy at first, but the accepted solution is built around one steady invariant. For 572. Subtree of Another Tree, the solution in this repository is mainly a two pointers solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are isSameTree, isSubtree, preorder, equals, traverse.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(m^2+n^2+m*n).
- Space: O(max(m,n)). The depth of the recursion tree can go upto n for tree t and m for tree s in worst case.
Guide
C++ Solution
Your submission
The accepted solution
01//Runtime: 32 ms, faster than 99.05% of C++ online submissions for Subtree of Another Tree.
02//Memory Usage: 20.9 MB, less than 99.03% of C++ online submissions for Subtree of Another Tree.
03
04/**
05 * Definition for a binary tree node.
06 * struct TreeNode {
07 * int val;
08 * TreeNode *left;
09 * TreeNode *right;
10 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11 * };
12 */
13class Solution {
14public:
15 bool isSameTree(TreeNode* s, TreeNode* t){
16 //this version not allow search t in s's subtree,
17 //it just compare whether s equals to t
18 if(!s && !t) return true;
19 if(!s || !t) return false;
20 if(s->val != t->val) return false;
21 return isSameTree(s->left, t->left) && isSameTree(s->right, t->right);
22 }
23 bool isSubtree(TreeNode* s, TreeNode* t) {
24 if(!s && !t) return true;
25 if(!s || !t) return false;
26 //both not empty
27 //s and t are same tree
28 if((s->val == t->val) && isSameTree(s->left, t->left) && isSameTree(s->right, t->right)) return true;
29 //if s and t are not the same,
30 //keep find t in s's subtree
31 return isSubtree(s->left, t) || isSubtree(s->right, t);
32 }
33};
34
35/**
36Approach #1 Using Preorder Traversal [Accepted]
37preorder traverse a tree and build a string
38then check for substring
39**/
40
41/**
42Complexity Analysis
43
44Time complexity : O(m^2+n^2+m*n).
45A total of nn nodes of the tree s and m nodes of tree t are traversed.
46Assuming string concatenation takes O(k) time for strings of length k and indexOf takes O(m*n).
47
48Space complexity : O(max(m,n)). The depth of the recursion tree can go upto n for tree t and m for tree s in worst case.
49**/
50
51/**
52class Solution {
53public:
54 string preorder(TreeNode* root, bool left){
55 if(!root){
56 if(left) return "null";
57 else return "null";
58 }
59 return "#" + to_string(root->val) + " " + preorder(root->left, true) + " " + preorder(root->right, false);
60 }
61 bool isSubtree(TreeNode* s, TreeNode* t) {
62 //if root is not NULL, then the 2nd parameter doesn't matter
63 string s1 = preorder(s, true);
64 string s2 = preorder(t, true);
65 return s1.find(s2)!=string::npos;
66 }
67};
68**/
69
70/**
71Approach #2 By Comparison of Nodes [Accepted]
72**/
73
74/**
75Complexity Analysis
76
77Time complexity : O(m*n)O(m∗n). In worst case(skewed tree) traverse function takes O(m*n)O(m∗n) time.
78
79Space complexity : O(n)O(n). The depth of the recursion tree can go upto nn. nn refers to the number of nodes in ss.
80**/
81
82/**
83class Solution {
84public:
85 bool equals(TreeNode* s, TreeNode* t){
86 if(!s && !t) return true;
87 if(!s || !t) return false;
88 return s->val == t->val && equals(s->left, t->left) && equals(s->right, t->right);
89 }
90 bool traverse(TreeNode* s, TreeNode* t){
91 if(s == NULL) return false;
92 return equals(s, t) || traverse(s->left, t) || traverse(s->right, t);
93 }
94 bool isSubtree(TreeNode* s, TreeNode* t) {
95 return traverse(s, t);
96 }
97};
98**/Cost