LeetCode in Kotlin

3997. Count Dominant Nodes in a Binary Tree

Medium

You are given the root of a complete binary tree.

A node x is called dominant if its value is equal to the maximum value among all nodes in the subtree rooted at x.

Return the number of dominant nodes in the tree.

Example 1:

Input: root = [5,3,8,2,4,7,1]

Output: 5

Explanation:

Example 2:

Input: root = [1,2,3,1,2]

Output: 4

Explanation:

Constraints:

Solution

import com_github_leetcode.TreeNode
import kotlin.math.max

/*
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private var dominantNode = 0

    fun countDominantNodes(root: TreeNode?): Int {
        dominantNode = 0
        dfs(root)
        return dominantNode
    }

    private fun dfs(root: TreeNode?): Int {
        if (root == null) {
            return Int.MIN_VALUE
        }
        if (root.left == null && root.right == null) {
            dominantNode++
            return root.`val`
        }
        val left = dfs(root.left)
        val right = dfs(root.right)
        val max = max(left, right)
        if (root.`val` >= max) {
            dominantNode++
        }
        return max(max, root.`val`)
    }
}