1448. Count Good Nodes in Binary Tree

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.

Solution:

/**
 * 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 {

    public int result = 0;
    public int goodNodes(TreeNode root) {
        int curMax = Integer.MIN_VALUE;
        helper(root, curMax);
        return result;
    }

    private void helper(TreeNode root, int curMax){
        if (root == null){
            return; 
        }

        if (root.val >= curMax){
            result++;
            curMax = root.val;
        }

        helper(root.left, curMax);
        helper(root.right, curMax);
    }


}


// TC: O(n)
// SC: O(n)

/**
 * 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 {
    int result = 0;
    public int goodNodes(TreeNode root) {

        dfs(root, Integer.MIN_VALUE);
        return result;
    }

    private void dfs(TreeNode node, int maxSoFar){
        if (maxSoFar <= node.val){
            result++;
        }

        if (node.right != null){
            dfs(node.right, Math.max(node.val, maxSoFar));
        }

        if (node.left != null){
            dfs(node.left, Math.max(node.val, maxSoFar));
        }
    }
}

// TC: O(n)
// SC: O(n)