This is one of those problems where the clean idea matters more than the amount of code. For 100. Same Tree, the solution in this repository is mainly a graph traversal solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. 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: graph traversal, two pointers, sliding window.
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, check.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The queue gives the solution a level-by-level or frontier-style traversal.
- 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(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given two binary trees, write a function to check if they are the same or not.
03
04Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
05
06Example 1:
07
08Input: 1 1
09 / \ / \
10 2 3 2 3
11
12 [1,2,3], [1,2,3]
13
14Output: true
15Example 2:
16
17Input: 1 1
18 / \
19 2 2
20
21 [1,2], [1,null,2]
22
23Output: false
24Example 3:
25
26Input: 1 1
27 / \ / \
28 2 1 1 2
29
30 [1,2,1], [1,1,2]
31
32Output: false
33**/
34
35//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Same Tree.
36//Memory Usage: 9.7 MB, less than 99.45% of C++ online submissions for Same Tree.
37
38/**
39 * Definition for a binary tree node.
40 * struct TreeNode {
41 * int val;
42 * TreeNode *left;
43 * TreeNode *right;
44 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
45 * };
46 */
47class Solution {
48public:
49 bool isSameTree(TreeNode* p, TreeNode* q) {
50 if(p == NULL && q == NULL){
51 return true;
52 }else if(p != NULL && q == NULL){
53 return false;
54 }else if(p == NULL && q != NULL){
55 return false;
56 }
57
58 return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
59 }
60};
61
62/**
63Approach 1: Recursion
64Intuition
65
66The simplest strategy here is to use recursion. Check if p and q nodes are not None, and their values are equal. If all checks are OK, do the same for the child nodes recursively.
67**/
68
69/**
70Complexity Analysis
71
72Time complexity : \mathcal{O}(N)O(N), where N is a number of nodes in the tree, since one visits each node exactly once.
73
74Space complexity : \mathcal{O}(\log(N))O(log(N)) in the best case of completely balanced tree and \mathcal{O}(N)O(N) in the worst case of completely unbalanced tree, to keep a recursion stack.
75**/
76
77/**
78Approach 2: Iteration
79Intuition
80
81Start from the root and then at each iteration pop the current node out of the deque. Then do the same checks as in the approach 1 :
82
83p and p are not None,
84
85p.val is equal to q.val,
86
87and if checks are OK, push the child nodes.
88**/
89
90/**
91Complexity Analysis
92
93Time complexity : \mathcal{O}(N)O(N) since each node is visited exactly once.
94
95Space complexity : \mathcal{O}(\log(N))O(log(N)) in the best case of completely balanced tree and \mathcal{O}(N)O(N) in the worst case of completely unbalanced tree, to keep a deque.
96**/
97
98/**
99class Solution {
100public:
101 bool check(TreeNode* p, TreeNode* q){
102 //this function check current node
103 if(p == NULL && q == NULL) return true;
104 if(p == NULL || q == NULL) return false;
105 if(p->val != q->val) return false;
106 return true;
107 }
108 bool isSameTree(TreeNode* p, TreeNode* q) {
109 //if check returns true, there are two cases needed to be handled differently
110 //if check returns false, just return false
111 if(p == NULL && q == NULL) return true;
112 if(!check(p, q)) return false;
113
114 queue<TreeNode*> q1, q2;
115
116 q1.push(p);
117 q2.push(q);
118
119 while(!q1.empty()){
120 p = q1.front(); q1.pop();
121 q = q2.front(); q2.pop();
122
123 if(p == NULL && q == NULL) continue;
124 if(!check(p, q)) return false;
125 //now both p and q are not NULL
126
127 if(!check(p->left, q->left)) return false;
128 if(p->left != NULL){
129 q1.push(p->left);
130 q2.push(q->left);
131 }
132
133 if(!check(p->right, q->right)) return false;
134 if(p->right != NULL){
135 q1.push(p->right);
136 q2.push(q->right);
137 }
138 }
139
140 return true;
141 }
142};
143**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.