1530. Number of Good Leaf Nodes Pairs LeetCode Solution

In this guide, you will get 1530. Number of Good Leaf Nodes Pairs LeetCode Solution with the best time and space complexity. The solution to Number of Good Leaf Nodes Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Number of Good Leaf Nodes Pairs solution in C++
Number of Good Leaf Nodes Pairs solution in Java
Number of Good Leaf Nodes Pairs solution in Python
Additional Resources

1530. Number of Good Leaf Nodes Pairs LeetCode Solution image

Problem Statement of 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 of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.
Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].

Constraints:

The number of nodes in the tree is in the range [1, 210].
1 <= Node.val <= 100
1 <= distance <= 10

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1530. Number of Good Leaf Nodes Pairs LeetCode Solution in C++

class Solution {
 public:
  int countPairs(TreeNode* root, int distance) {
    int ans = 0;

    dfs(root, distance, ans);

    return ans;
  }

 private:
  vector<int> dfs(TreeNode* root, int distance, int& ans) {
    vector<int> d(distance + 1);  // {distance: the number of leaf nodes}
    if (root == nullptr)
      return d;
    if (root->left == nullptr && root->right == nullptr) {
      d[0] = 1;
      return d;
    }

    const vector<int> dl = dfs(root->left, distance, ans);
    const vector<int> dr = dfs(root->right, distance, ans);

    for (int i = 0; i < distance; ++i)
      for (int j = 0; j < distance; ++j)
        if (i + j + 2 <= distance)
          ans += dl[i] * dr[j];

    for (int i = 0; i < distance; ++i)
      d[i + 1] = dl[i] + dr[i];

    return d;
  }
};
/* code provided by PROGIEZ */

1530. Number of Good Leaf Nodes Pairs LeetCode Solution in Java

class Solution {
  public int countPairs(TreeNode root, int distance) {
    dfs(root, distance);

    return ans;
  }

  private int ans = 0;

  private int[] dfs(TreeNode root, int distance) {
    int[] d = new int[distance + 1]; // {distance: the number of leaf nodes}
    if (root == null)
      return d;
    if (root.left == null && root.right == null) {
      d[0] = 1;
      return d;
    }

    int[] dl = dfs(root.left, distance);
    int[] dr = dfs(root.right, distance);

    for (int i = 0; i < distance; ++i)
      for (int j = 0; j < distance; ++j)
        if (i + j + 2 <= distance)
          ans += dl[i] * dr[j];

    for (int i = 0; i < distance; ++i)
      d[i + 1] = dl[i] + dr[i];

    return d;
  }
}
// code provided by PROGIEZ