344. Values Inside a Range
Foundation1000 ms256 MBSolved by 0%
Print how many nodes hold a value between lo and hi, with both ends
included.
Nothing here needs a search tree, so walk every node and count the ones that qualify. The traversal order does not matter.
Both bounds are inclusive, so a value exactly equal to lo or hi counts.
The range may also be a single point, where lo and hi are equal.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ lo ≤ hi ≤ 1000000000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains three integers n, lo and hi.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains the left and right child of node i,
using 0 for no child. Node 1 is the root.
Output
Print one integer, the number of nodes whose value lies in the range.
Input7 2 6
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output5
Noteincludes both endpoints, so 2 and 6 both count
Input7 1 1
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output1
Noteis a single-point range
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.