1448. 统计二叉树中好节点的数目 - Kotlin 深度优先搜索

Problem: 1448. 统计二叉树中好节点的数目

思路

基于深度优先搜索的思路，在递归函数goodNodes中每次传入从根节点到当前节点的最大值，则以当前节点为根的子树的好节点数量为左子树的好节点数量+右子树的好节点数量+当前节点是否为好节点，即goodNodes(root.left,maxNow)+goodNodes(root.Right,maxNow)+ (maxNow > root.val)?0:1

递归的回归条件：当当前节点为null时，直接返回0即可

复杂度

• 时间复杂度:

• 空间复杂度:

Code

class Solution
fun Solution.goodNodes(root: TreeNode?, maxNow: Int = Int.MIN_VALUE): Int =
    if (root == null) 0
    else goodNodes(root.left, Math.max(maxNow, root.`val`)) +
            goodNodes(root.right, Math.max(maxNow, root.`val`)) +
            if (maxNow > root.`val`) 0 else 1