Untitled

 avatar
unknown
plain_text
a month ago
1.8 kB
1
Indexable
class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int value) {
        val = value;
        left = right = null;
    }
}

public class GoodNodes {

    private int goodNodesCount = 0;

    public int goodNodes(TreeNode root) {
        dfs(root, Integer.MIN_VALUE);  // Start DFS from the root with the minimum possible value
        return goodNodesCount;
    }

    private void dfs(TreeNode node, int maxSoFar) {
        if (node == null) {
            return;
        }

        // If the current node's value is greater than or equal to the maximum value in the path, it's a good node
        if (node.val >= maxSoFar) {
            goodNodesCount++;
        }

        // Update the maxSoFar to be the maximum of the current node's value and the current maxSoFar
        int newMax = Math.max(maxSoFar, node.val);

        // Recursively traverse the left and right subtrees
        dfs(node.left, newMax);
        dfs(node.right, newMax);
    }

    public static void main(String[] args) {
        // Example 1
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(1);
        root1.right = new TreeNode(4);
        root1.left.left = new TreeNode(3);
        root1.right.left = new TreeNode(1);
        root1.right.right = new TreeNode(5);

        GoodNodes sol = new GoodNodes();
        System.out.println(sol.goodNodes(root1));  // Output: 4

        // Example 2
        TreeNode root2 = new TreeNode(3);
        root2.left = new TreeNode(3);
        root2.left.left = new TreeNode(4);
        root2.left.right = new TreeNode(2);

        System.out.println(sol.goodNodes(root2));  // Output: 3

        // Example 3
        TreeNode root3 = new TreeNode(1);

        System.out.println(sol.goodNodes(root3));  // Output: 1
    }
}
Leave a Comment