1448. Count Good Nodes in Binary Tree

[songyy5517]

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.

Intuition This problem is to find out all the nodes that is the maximum on the path from the root node to itself. A simple idea is to travarse all the nodes with DFS, and then for each node determine whether it is a good node. The key here is how to determine whether a node is good or not. We can keep a variable to record the maximum node value on the path from root to the current node. If the current node is greater than the maximum node value, then it is a good node, and we update the maximum node value.

[songyy5517]

Approach: DFS

1. Exception handling;
2. Define a global variable num to record the number of good nodes;
3. Travarse the whole tree using DFS with the maximum node value set to the value of the root node;
   • If the current node is greater than the maximum node value, then add 1 to the number of good nodes and update the maximum node value;
4. Return the number of good numbers.

Complexity Analysis

• Time complexity: $O(N)$ , iterating over all the nodes requires $O(N)$ time;
• Space complexity: $O(N)$ , the binary tree would degrade into a linked list under the worst circumstance, which would case the recursion depth to be $N$ , taking up $O(N)$ stack space.

[songyy5517]

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

        dfs(root, root.val);
        return num;
    }

    void dfs(TreeNode root, int max){
        if (root == null)
            return ;

        if (root.val >= max)
            num ++;

        dfs(root.left, Math.max(root.val, max));
        dfs(root.right, Math.max(root.val, max));
    }
}

[songyy5517]

2024/6/1