This is one of those problems where the clean idea matters more than the amount of code. For 1530. Number of Good Leaf Nodes Pairs, the solution in this repository is mainly a DFS + memoization 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: DFS + memoization, graph traversal, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- only go up or bottom-right, this cannot work
- WA
- 47 / 113 test cases passed.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are buildParents, findGoodPairs, countPairs, buildParentsAndLeaves, helper.
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.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- 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//only go up or bottom-right, this cannot work
02//WA
03//47 / 113 test cases passed.
04/**
05 * Definition for a binary tree node.
06 * struct TreeNode {
07 * int val;
08 * TreeNode *left;
09 * TreeNode *right;
10 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
11 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13 * };
14 */
15class Solution {
16public:
17 vector<TreeNode*> leaves;
18 unordered_map<TreeNode*, TreeNode*> parents;
19 int ans;
20
21 void buildParents(TreeNode* node, TreeNode* parent){
22 parents[node] = parent;
23 if(!node->left && !node->right) leaves.push_back(node);
24 if(node->left) buildParents(node->left, node);
25 if(node->right) buildParents(node->right, node);
26 };
27
28 void findGoodPairs(TreeNode* node, TreeNode* last, int distance){
29 //either go up or go bottom-right
30 if(distance < 0) return;
31 if(last && !node->left && !node->right) ++ans;
32
33 if(parents[node] && parents[node] != last){
34 findGoodPairs(parents[node], node, distance-1);
35 }
36 if(node->right && node->right != last){
37 findGoodPairs(node->right, node, distance-1);
38 }
39 }
40
41 int countPairs(TreeNode* root, int distance) {
42 buildParents(root, nullptr);
43
44 ans = 0;
45
46 for(TreeNode* leaf : leaves){
47 findGoodPairs(leaf, nullptr, distance);
48 }
49
50 return ans;
51 }
52};
53
54//dfs, use visited array
55//Runtime: 680 ms, faster than 7.28% of C++ online submissions for Number of Good Leaf Nodes Pairs.
56//Memory Usage: 92.3 MB, less than 6.17% of C++ online submissions for Number of Good Leaf Nodes Pairs.
57/**
58 * Definition for a binary tree node.
59 * struct TreeNode {
60 * int val;
61 * TreeNode *left;
62 * TreeNode *right;
63 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
64 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
65 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
66 * };
67 */
68class Solution {
69public:
70 set<TreeNode*> visited;
71 vector<TreeNode*> leaves;
72 unordered_map<TreeNode*, TreeNode*> parents;
73 int ans;
74
75 void buildParentsAndLeaves(TreeNode* node, TreeNode* parent){
76 parents[node] = parent;
77 if(!node->left && !node->right) leaves.push_back(node);
78 if(node->left) buildParentsAndLeaves(node->left, node);
79 if(node->right) buildParentsAndLeaves(node->right, node);
80 };
81
82 void findGoodPairs(TreeNode* node, TreeNode* last, int distance){
83 if(distance < 0) return;
84 //if(last): it's not source
85 if(last && !node->left && !node->right) ++ans;
86
87 if(parents[node] && visited.find(parents[node]) == visited.end()){
88 visited.insert(parents[node]);
89 findGoodPairs(parents[node], node, distance-1);
90 }
91 if(node->right && visited.find(node->right) == visited.end()){
92 visited.insert(node->right);
93 findGoodPairs(node->right, node, distance-1);
94 }
95 //need to go left!
96 if(node->left && visited.find(node->left) == visited.end()){
97 visited.insert(node->left);
98 findGoodPairs(node->left, node, distance-1);
99 }
100 }
101
102 int countPairs(TreeNode* root, int distance) {
103 buildParentsAndLeaves(root, nullptr);
104
105 ans = 0;
106
107 // cout << "leaves: ";
108 // for(TreeNode* leaf : leaves){
109 // cout << leaf->val << " ";
110 // }
111 // cout << endl;
112
113 for(TreeNode* leaf : leaves){
114 visited.insert(leaf);
115 findGoodPairs(leaf, nullptr, distance);
116 visited.clear();
117 }
118
119 return ans>>1;
120 }
121};
122
123//Post order traversal
124//https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/discuss/755784/Java-Detailed-Explanation-Post-Order-Cache-in-Array
125//Runtime: 128 ms, faster than 57.60% of C++ online submissions for Number of Good Leaf Nodes Pairs.
126//Memory Usage: 35.4 MB, less than 68.22% of C++ online submissions for Number of Good Leaf Nodes Pairs.
127/**
128 * Definition for a binary tree node.
129 * struct TreeNode {
130 * int val;
131 * TreeNode *left;
132 * TreeNode *right;
133 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
134 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
135 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
136 * };
137 */
138class Solution {
139public:
140 int ans;
141
142 vector<int> helper(TreeNode* node, int distance){
143 //i: the distance from node's PARENT to leaves
144 //dist2counts[i]: such leaves' count
145 //from problem description, 0 <= distance <= 10, so we only need a length 11 array
146 vector<int> dist2counts(11, 0);
147
148 if(!node) return dist2counts;
149
150 if(!node->left && !node->right){
151 //first 1 : PARENT to current node's distance
152 //second 1: the count is one
153 dist2counts[1] = 1;
154 return dist2counts;
155 }
156
157 vector<int> left = helper(node->left, distance);
158 vector<int> right = helper(node->right, distance);
159
160 for(int i = 0; i < 10; ++i){
161 //left[i]: starting from current node, there are left[i] leaves distance i
162 //i+1: distance from node to leaf + distance from node's parent to node
163 dist2counts[i+1] += left[i]+right[i];
164 }
165
166 for(int i = 0; i <= 10; ++i){
167 for(int j = 0; i+j <= distance; ++j){
168 //i and j are distance from current node to leaves
169 ans += (left[i]*right[j]);
170 }
171 }
172
173 // cout << "node: " << node->val << endl;
174 // for(int i = 0; i < 11; ++i){
175 // cout << left[i] << " ";
176 // }
177 // cout << endl;
178 // for(int i = 0; i < 11; ++i){
179 // cout << right[i] << " ";
180 // }
181 // cout << endl;
182 // for(int i = 0; i < 11; ++i){
183 // cout << dist2counts[i] << " ";
184 // }
185 // cout << endl;
186 return dist2counts;
187 };
188
189 int countPairs(TreeNode* root, int distance) {
190 ans = 0;
191 helper(root, distance);
192 return ans;
193 }
194};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.