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:
tree is in the range [1, 210].1 <= Node.val <= 1001 <= distance <= 10This approach involves a DFS traversal of the tree. For each node, we compute the number of leaf nodes at each possible distance. We merge the results from the left and right subtrees and count the valid leaf pairs.
In this C implementation of the DFS approach, we maintain arrays to count leaf nodes at particular distances for each subtree. We combine these left and right arrays for each node and calculate valid pairs within the distance constraint. The result is accumulated during the traversal.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * distance) due to traversing the entire tree and computing leaf pairs.
Space Complexity: O(distance) for storing distance arrays.
This approach leverages preprocessing leaf distances in a dynamic programming table, which gives quick lookups during pair evaluation. It builds the DP table during a DFS traversal, allowing efficient pair computation afterward.
A solution in C would involve more detailed memory management and array calculations for storing and evaluating distances.
C++
Java
Python
Time Complexity: Approximately O(n^2) for thorough pairing and evaluation.
Space Complexity: O(n^2) due to pair-wise distance visualization.
| Approach | Complexity |
|---|---|
| DFS with Distance Array | Time Complexity: O(n * distance) due to traversing the entire tree and computing leaf pairs. |
| Preprocessing with Dynamic Programming | Time Complexity: Approximately O(n^2) for thorough pairing and evaluation. |
Leetcode 1530. Number of Good Leaf Nodes Pairs • Fraz • 12,760 views views
Watch 9 more video solutions →Practice Number of Good Leaf Nodes Pairs with our built-in code editor and test cases.
Practice on FleetCode