[leetcode #1448] Count Good Nodes in Binary Tree

Problem

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 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

Constraints:

・ The number of nodes in the binary tree is in the range [1, 10⁵].
・ Each node's value is between [-10⁴, 10⁴].

Idea

난이도는 medium으로 되어 있으나 문제를 풀다보면 easy라는 생각이 드는 문제다. 알고리즘은 다음과 같다.

1. Tree를 탐색하면서 해당 path의 최대값을 넘겨준다.
2. 현재 node의 값이 최대값보다 크거나 같을 경우 리턴할 값에 1을 더하고 최대값을 node의 값으로 바꾼다.
3. 모든 tree를 탐색한 후 값을 리턴한다.

Solution

class Solution {
    int ans;

    public int goodNodes(TreeNode root) {
        traverseTree(root, Integer.MIN_VALUE);

        return ans;
    }

    private void traverseTree(TreeNode node, int maxValue) {
        if (node == null)
            return;

        if (node.val >= maxValue) {
            ans++;
            maxValue = node.val;
        }
        traverseTree(node.left, maxValue);
        traverseTree(node.right, maxValue);
    }
}

Reference

https://leetcode.com/problems/count-good-nodes-in-binary-tree/