Untitled
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