Leetcode 1530: Number of Good Leaf Nodes Pairs
You are given the root of a binary tree and an integer distance. A pair of two different leaf nodes is considered good if the shortest path between them is less than or equal to the given distance. The task is to return the number of such good leaf node pairs in the tree.
Problem
Approach
Steps
Complexity
Input: The input consists of a binary tree with nodes containing integer values, and an integer distance.
Example: root = [1, 2, 3, null, 4], distance = 3
Constraints:
• 1 <= Node.val <= 100
• 1 <= distance <= 10
• The number of nodes in the tree is in the range [1, 210].
Output: Return the number of good leaf node pairs in the tree, where the shortest path between the pair is less than or equal to the given distance.
Example: For root = [1, 2, 3, null, 4] and distance = 3, the output is 1.
Constraints:
• The output is the number of good leaf node pairs in the tree.
Goal: The goal is to count the good leaf node pairs in the binary tree.
Steps:
• Traverse the tree and for each leaf node, calculate the distance to other leaf nodes.
• For each pair of leaf nodes, check if the distance between them is less than or equal to the given distance.
• Count the number of such pairs.
Goal: The solution should be able to handle up to 210 nodes efficiently.
Steps:
• 1 <= Node.val <= 100
• 1 <= distance <= 10
• The number of nodes in the tree is in the range [1, 210].
Assumptions:
• The tree contains at least one node.
• The leaf nodes are at the deepest levels of the tree.
• Input: root = [1, 2, 3, null, 4], distance = 3
• Explanation: The leaf nodes 3 and 4 are the only good pair, as the shortest path between them is 3.
• Input: root = [1, 2, 3, 4, 5, 6, 7], distance = 3
• Explanation: The good pairs are [4, 5] and [6, 7] with shortest path 2. Pair [4, 6] is not good due to a distance of 4.
Approach: To solve the problem, a depth-first search (DFS) approach can be used to traverse the tree and calculate distances between leaf nodes.
Observations:
• We need to calculate the shortest paths between pairs of leaf nodes.
• Using DFS, we can explore the tree and collect the depths of leaf nodes, then compare the distances between them.
Steps:
• Perform a DFS to traverse the tree, collecting the number of leaf nodes at each level.
• For each pair of leaf nodes, check if their shortest path is less than or equal to the given distance.
• Count the number of such pairs and return the result.
Empty Inputs:
• No empty tree inputs as the tree contains at least one node.
Large Inputs:
• Ensure the solution works efficiently for trees with up to 210 nodes.
Special Values:
• Handle trees with only one leaf node.
Constraints:
• The tree structure should be a valid binary tree.
int ans = 0;
int countPairs(TreeNode* root, int dist) {
dfs(root, dist);
return ans;
}
vector<int> dfs(TreeNode* root, int dist) {
if(!root) {
vector<int> res(dist + 1, 0);
return res;
}
if(root->left == NULL && root->right == NULL) {
vector<int> res(dist + 1, 0);
res[1]++;
return res;
}
vector<int> left = dfs(root->left, dist);
vector<int> right = dfs(root->right, dist);
for(int i = 1; i <= dist - 1; i++) {
for(int j = dist - 1; j >= 1; j--) {
if(i + j <= dist)
ans += left[i] * right[j];
}
}
vector<int> res(dist + 1, 0);
for(int i = 1; i <= dist - 2; i++ ) {
res[i + 1] = left[i] + right[i];
}
return res;
}
1 : Variable Initialization
int ans = 0;
The variable `ans` is initialized to zero. This will store the total number of valid leaf node pairs that satisfy the distance condition.
2 : Function Declaration
int countPairs(TreeNode* root, int dist) {
This is the declaration of the `countPairs` function. It takes a pointer to the root of the binary tree and the maximum allowed distance between the leaf nodes and returns the number of valid leaf node pairs.
3 : DFS Call
dfs(root, dist);
The `dfs` function is called to traverse the tree and calculate the distances for each node. It also counts the pairs that meet the distance constraint.
4 : Return Result
return ans;
After the traversal, the total count of valid leaf node pairs is returned.
5 : DFS Function Declaration
vector<int> dfs(TreeNode* root, int dist) {
This is the declaration of the `dfs` function. It takes a pointer to the current tree node and the maximum allowed distance and returns a vector of integers representing the counts of leaf nodes at each distance.
6 : Base Case for Null Node
if(!root) {
If the current node is null, an empty vector with `dist + 1` elements, all set to zero, is returned. This serves as the base case for the recursion.
7 : Initialize Result Vector
vector<int> res(dist + 1, 0);
A vector `res` of size `dist + 1` is initialized with zeros. This vector will store the count of leaf nodes at each distance.
8 : Return Result for Null Node
return res;
The function returns the initialized result vector when the node is null.
9 : Leaf Node Check
if(root->left == NULL && root->right == NULL) {
If the current node is a leaf node (both left and right children are null), the function proceeds to count it as a valid leaf node at distance 1.
10 : Initialize Leaf Result
vector<int> res(dist + 1, 0);
A new result vector `res` is initialized to store the count of leaf nodes at each distance for the current leaf node.
11 : Increment Leaf Distance
res[1]++;
Since this is a leaf node, the count for distance 1 is incremented by 1.
12 : Return Leaf Node Result
return res;
The result vector is returned for the leaf node.
13 : Recursive DFS Call for Left Subtree
vector<int> left = dfs(root->left, dist);
The `dfs` function is recursively called for the left subtree of the current node, and the result is stored in the vector `left`.
14 : Recursive DFS Call for Right Subtree
vector<int> right = dfs(root->right, dist);
The `dfs` function is recursively called for the right subtree of the current node, and the result is stored in the vector `right`.
15 : Pair Count Calculation
for(int i = 1; i <= dist - 1; i++) {
This loop iterates through possible distances from the left subtree.
16 : Nested Pair Count Calculation
for(int j = dist - 1; j >= 1; j--) {
This nested loop iterates through possible distances from the right subtree.
17 : Add Valid Pairs to Answer
if(i + j <= dist)
If the sum of the current distances from both subtrees is less than or equal to the maximum distance `dist`, the product of the counts of nodes at these distances is added to the `ans` variable.
18 : Increment Answer with Pairs
ans += left[i] * right[j];
The result from the pair calculation is added to the global `ans` variable.
19 : Initialize Result Vector for Distances
vector<int> res(dist + 1, 0);
A new result vector `res` is initialized to store the updated counts of leaf nodes at each distance after processing both subtrees.
20 : Combine Left and Right Subtree Results
for(int i = 1; i <= dist - 2; i++ ) {
This loop combines the results from the left and right subtrees for each distance.
21 : Update Combined Result Vector
res[i + 1] = left[i] + right[i];
The count for each distance is updated by adding the counts from the left and right subtrees.
22 : Return Combined Result
return res;
The combined result vector, representing the updated counts of leaf nodes at each distance, is returned.
Best Case: O(n)
Average Case: O(n log n)
Worst Case: O(n^2)
Description: The worst-case time complexity is O(n^2) when comparing all pairs of leaf nodes.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the recursive DFS stack and storing leaf nodes.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus