Link:- https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/
Summary:
Given a root of the binary tree and an integer distance. Find the number of pairs of leaves such that the shortest path between them is less than or equal to distance.
For Example:
Input:
root = [1,2,3,null,4], distance = 3
Output:
1
Logic:
Convert the binary tree into a graph using DFS and find all the leaves in that DFS traversal.
Run other DFS from each leaf and check if the shortest distance between current leave and other leaf is less than or equal to distance or not.
If yes:
ans++
Finally, return ans/2.
Why ans/2?
As we run DFS from each leaf, we end up computing the same pair of leaves twice.
Time Complexity:
O(n^2)
To view my solution:
No comments:
Post a Comment