[LeetCode] 1448. Count Good Nodes in Binary Tree

1. Question

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.

2. Thoughts

Use DFS

3. Tips learned

4. My solution

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, path_max):
            if not node:
                return 0

            return_val = dfs(node.left, max(path_max, node.val)) + dfs(
                node.right, max(path_max, node.val)
            )

            if node.val >= path_max:
                return_val += 1

            return return_val

        return dfs(root, root.val)

63/63 cases passed (207 ms)
Your runtime beats 21.06 % of python3 submissions
Your memory usage beats 15.44 % of python3 submissions (35.1 MB)

5. AI Solution and Improvements

Your solution for counting the number of good nodes in a binary tree is quite efficient and follows the right approach using depth-first search (DFS). However, there's a small optimization you can make to simplify the code.

Suggested Improvement

You can directly increment the count of good nodes within the recursive call instead of using a separate return_val variable. This makes the code slightly more concise and easier to follow. Here's the revised version of your solution:

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, path_max):
            if not node:
                return 0

            # Increment if the current node is a 'good' node
            count = 1 if node.val >= path_max else 0

            # Update the path maximum for the left and right subtrees
            path_max = max(path_max, node.val)
            count += dfs(node.left, path_max)
            count += dfs(node.right, path_max)

            return count

        return dfs(root, root.val)

Explanation

• DFS Function: The dfs function is a recursive function that traverses the tree. It takes two arguments: the current node and the maximum value found in the path up to that node (path_max).

• Counting Good Nodes: If the current node's value is greater than or equal to path_max, it's considered a good node, and the count is incremented.

• Updating Path Maximum: The path maximum is updated to the maximum of the current path_max and the current node's value. This updated path_max is passed to the recursive calls for the left and right children.

• Recursive Calls: The function then recursively calls itself for the left and right children, adding their counts of good nodes to the total count.

Benefits of the Improved Solution

• Clarity: The code is more straightforward and easy to understand.
• Efficiency: The logic is optimized by directly counting good nodes in the recursive calls, reducing the need for additional variables.
• Readability: The simplified approach makes the code more readable and easier to maintain.