Count Good Nodes in Binary Tree

1package pkg5leetcode.official75;2 3/*4 * Count Good Nodes in Binary Tree | LC 14485 * APPROACH: DFS count nodes >= max on path from root.6 * COMPLEXITY: Time O(n), Space O(h)7 */8public class official75_LC1448CountGoodNodesInBinaryTree {9    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */10 11    static class TreeNode {12        int val;13        TreeNode left, right;14        TreeNode(int val) { this.val = val; }15    }16 17    static int goodNodes(TreeNode root) {18        return dfs(root, root.val);19    }20 21    static int dfs(TreeNode node, int maxSoFar) {22        if (node == null) return 0;23        int count = node.val >= maxSoFar ? 1 : 0;24        maxSoFar = Math.max(maxSoFar, node.val);25        return count + dfs(node.left, maxSoFar) + dfs(node.right, maxSoFar);26    }27 28    public static void main(String[] args) {29        TreeNode root = new TreeNode(3);30        root.left = new TreeNode(1); root.right = new TreeNode(4);31        root.left.left = new TreeNode(3); root.right.left = new TreeNode(1);32        root.right.right = new TreeNode(5);33        check(goodNodes(root) == 4, "case1");34        TreeNode r2 = new TreeNode(3); r2.left = new TreeNode(3);35        r2.right = new TreeNode(4); r2.right.left = new TreeNode(2);36        check(goodNodes(r2) == 3, "case2");37        System.out.println("all tests passed");38    }39 40    static void check(boolean cond, String name) {41        if (!cond) throw new AssertionError("FAILED: " + name);42        System.out.println("  PASS " + name);43    }44}