Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.
Return the number of good nodes in the binary tree.
Example 1:
Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun goodNodes(root: TreeNode?): Int {
if (root == null) {
return 0
}
return findGoodNode(root, root.`val`)
}
}
private fun findGoodNode(root: TreeNode?, maxValue: Int): Int {
if (root == null) {
return 0
}
if (root.`val` < maxValue) {
return findGoodNode(root?.left, maxValue) + findGoodNode(root.right, maxValue)
} else {
return 1+ findGoodNode(root?.left, root.`val`) + findGoodNode(root.right, root.`val`)
}
}