This article has participated in the Denver Nuggets Creators Camp 3 “More Productive writing” track, see details: Digg project | creators Camp 3 ongoing, “write” personal impact

describe

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.
Copy the code

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.
Copy the code

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.
Copy the code

Note:

The number of nodes in the binary tree is in the range [1, 10^5].
Each node's value is between [-10^4, 10^4].
Copy the code

parsing

Given a binary tree root, find out how many nodes in the middle of the tree are good. The definition of “good node” in the question is that the value of nodes on the path from this node to the root node is less than or equal to this node. The idea is relatively simple. DFS is directly used to pass in the maximum value in the current path during recursion, and then compare with the current value. If it meets the meaning of the question, result is added by one, and result at the end of recursion is the answer.

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def __init__(self):
        self.result = 0

    def goodNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0

        def dfs(root, maxValue):
            if not root:
                return
            maxValue = max(maxValue, root.val)
            if root.val >= maxValue:
                self.result += 1
            dfs(root.left, maxValue)
            dfs(root.right, maxValue)
            
        dfs(root, root.val)
        return self.result

        	      
		
Copy the code

The results

Given the node in the linked list. Memory Usage: 10000 ms Submissions in the Python online list for Count Good Nodes in Binary Tree.Copy the code

parsing

Instead of using the global variable self.result, calculate the result recursively.

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def goodNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root or (not root.left and not root.right):
            return 1

        def dfs(root, maxValue):
            if not root:
                return 0
            maxValue = max(maxValue, root.val)
            count = 1 if root.val >= maxValue else 0
            return count + dfs(root.left, maxValue) + dfs(root.right, maxValue)

        return dfs(root, root.val)
Copy the code

The results

Each node in the linked list is linked to the node in the linked list. Submissions in the Python online list for Count Good Nodes in Binary Tree.Copy the code

Original link: leetcode.com/problems/co…

Your support is my biggest motivation