Count Good Nodes in Binary Tree
MediumThe problem
Walk from the root down to a node X. X is "good" if no node on that path has a value bigger than X. Return how many good nodes the tree has (the root always counts).
- Example 1Input: root = [3, 1, 4, 3, null, 1, 5]Output: 4
Good nodes are 3 (root), 4, the 3 under the 1, and 5. The two 1s are smaller than a 3 above them.
- Example 2Input: root = [3, 3, null, 4, 2]Output: 3
The root 3, the second 3 and the 4 are good. The 2 is not, because 3 and 4 are above it.
- 1 ≤ number of nodes ≤ 100,000
- -10,000 ≤ node value ≤ 10,000
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
A node is good based on the path from the root. What information do you carry down?
The idea
DFS passing the maximum value seen on the path; if node ≥ max it is good; pass max(max, node) to children.
Target: O(n) time
Go function shape
func goodNodes(root *TreeNode) intReference solution
Tested with go test. Try it yourself first, then compare.
// GoodNodes: a node is good if no node on the path from the root is larger. Carry the path maximum downward.
func GoodNodes(root *TreeNode) int {
var dfs func(n *TreeNode, pathMax int) int
dfs = func(n *TreeNode, pathMax int) int {
if n == nil {
return 0
}
count := 0
if n.Val >= pathMax {
count = 1
}
pathMax = max(pathMax, n.Val)
return count + dfs(n.Left, pathMax) + dfs(n.Right, pathMax)
}
if root == nil {
return 0
}
return dfs(root, root.Val)
}