Let's make this one less mysterious. For 865. Smallest Subtree with all the Deepest Nodesl, 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, 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 subtreeWithAllDeepest, dfs, answer.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- 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:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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//Runtime: 4 ms, faster than 86.00% of C++ online submissions for Smallest Subtree with all the Deepest Nodes.
02//Memory Usage: 13.7 MB, less than 100.00% of C++ online submissions for Smallest Subtree with all the Deepest Nodes.
03/**
04 * Definition for a binary tree node.
05 * struct TreeNode {
06 * int val;
07 * TreeNode *left;
08 * TreeNode *right;
09 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 * };
11 */
12class Solution {
13public:
14 TreeNode* subtreeWithAllDeepest(TreeNode* root) {
15 unordered_map<TreeNode*, TreeNode*> parent;
16 TreeNode* cur;
17 queue<TreeNode*> q;
18 vector<TreeNode*> levelNodes, nextLevelNodes;
19 int levelCount = 0, nextLevelCount = 0;
20
21 q.push(root);
22 parent[root] = nullptr;
23 levelCount = 1;
24 levelNodes.push_back(root);
25
26 while(!q.empty()){
27 cur = q.front(); q.pop();
28
29 if(cur->left){
30 q.push(cur->left);
31 nextLevelCount++;
32 nextLevelNodes.push_back(cur->left);
33 parent[cur->left] = cur;
34 }
35
36 if(cur->right){
37 q.push(cur->right);
38 nextLevelCount++;
39 nextLevelNodes.push_back(cur->right);
40 parent[cur->right] = cur;
41 }
42
43 levelCount--;
44 //update level info if we are not at deepest level
45 //(we still have children)
46 if(levelCount == 0 && nextLevelCount > 0){
47 levelCount = nextLevelCount;
48 nextLevelCount = 0;
49 levelNodes = nextLevelNodes;
50 nextLevelNodes.clear();
51 // cout << "levelCount: " << levelCount << endl;
52 }
53
54 }
55
56 // cout << levelNodes.size() << endl;
57 // for(int i = 0; i < levelNodes.size(); i++){
58 // cout << levelNodes[i]->val << " ";
59 // }
60 // cout << endl;
61
62 //now levelNodes contains the deepest nodes
63 while(true){
64 cur = levelNodes[0];
65 bool allSame = true;
66 for(int i = 1; i < levelNodes.size(); i++){
67 if(cur != levelNodes[i]){
68 allSame = false;
69 break;
70 }
71 }
72 if(allSame){
73 return cur;
74 }
75 //move all nodes one level up
76 for(int i = 0; i < levelNodes.size(); i++){
77 levelNodes[i] = parent[levelNodes[i]];
78 }
79 }
80
81 return nullptr;
82 }
83};
84
85//DFS, recursion
86//Runtime: 4 ms, faster than 86.00% of C++ online submissions for Smallest Subtree with all the Deepest Nodes.
87//Memory Usage: 15.7 MB, less than 7.14% of C++ online submissions for Smallest Subtree with all the Deepest Nodes.
88//time: O(N), space: O(N)
89/**
90 * Definition for a binary tree node.
91 * struct TreeNode {
92 * int val;
93 * TreeNode *left;
94 * TreeNode *right;
95 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
96 * };
97 */
98class Solution {
99public:
100 unordered_map<TreeNode*, int> depth;
101 int maxDepth;
102
103 void dfs(TreeNode* node, TreeNode* parent){
104 if(node == nullptr) return;
105 depth[node] = depth[parent] + 1;
106 maxDepth = max(maxDepth, depth[node]);
107 dfs(node->left, node);
108 dfs(node->right, node);
109 };
110
111 TreeNode* answer(TreeNode* node){
112 //the return value nullptr will be ignored by its caller
113 if(node == nullptr) return node;
114 if(depth[node] == maxDepth) return node;
115 TreeNode *L = answer(node->left);
116 TreeNode *R = answer(node->right);
117 if(L && R) return node;
118 if(L) return L;
119 if(R) return R;
120 return nullptr;
121 };
122
123 TreeNode* subtreeWithAllDeepest(TreeNode* root) {
124 maxDepth = -1;
125 /*root's parent is nullptr,
126 we want root's depth be 0, so nullptr's depth should be -1
127 */
128 depth[nullptr] = -1;
129 dfs(root, nullptr);
130
131 return answer(root);
132 }
133};
134
135//Recursion
136//Runtime: 4 ms, faster than 86.00% of C++ online submissions for Smallest Subtree with all the Deepest Nodes.
137//Memory Usage: 13.2 MB, less than 100.00% of C++ online submissions for Smallest Subtree with all the Deepest Nodes.
138//time: O(N), space: O(N)
139/**
140 * Definition for a binary tree node.
141 * struct TreeNode {
142 * int val;
143 * TreeNode *left;
144 * TreeNode *right;
145 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
146 * };
147 */
148class Solution {
149public:
150 pair<TreeNode*, int> dfs(TreeNode* node){
151 /*
152 calculate depth from bottom:
153 null node has depth 0, leaf node has depth 1, ...
154 we return the child with larger depth
155 */
156 if(!node) return make_pair(nullptr, 0);
157 pair<TreeNode*, int> L = dfs(node->left);
158 pair<TreeNode*, int> R = dfs(node->right);
159 if(L.second > R.second) return make_pair(L.first, L.second+1);
160 if(L.second < R.second) return make_pair(R.first, R.second+1);
161 //L.second and R.second are equal
162 return make_pair(node, L.second+1);
163 };
164
165 TreeNode* subtreeWithAllDeepest(TreeNode* root) {
166 return dfs(root).first;
167 }
168};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.