1448 Count Good Nodes in Binary Tree

Warning

This post is more than a year old. Information may be outdated.

Solved at: 220827

Question

Given a binary tree root, a node X in the tree is named good if in the path from the root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Solution

python

class Solution:    def countGoodNodes(self, node: TreeNode, maxVal: int) -> int:        if not node:            return 0        count = 0        if not maxVal > node.val:            count += 1        if node.val > maxVal:            maxVal = node.val        count = count + self.countGoodNodes(node.left, maxVal) + self.countGoodNodes(node.right, maxVal)        return count
    def goodNodes(self, root: TreeNode) -> int:        return self.countGoodNodes(root, root.val)

class Solution:    def countGoodNodes(self, node: TreeNode, maxVal: int) -> int:        if not node:            return 0        count = 0        if not maxVal > node.val:            count += 1        if node.val > maxVal:            maxVal = node.val        count = count + self.countGoodNodes(node.left, maxVal) + self.countGoodNodes(node.right, maxVal)        return count
    def goodNodes(self, root: TreeNode) -> int:        return self.countGoodNodes(root, root.val)

Results

Runtime

436 ms, faster than 36.72% of Python3 online submissions for Count Good Nodes in Binary Tree.

Memory Usage

32.6 MB, less than 45.65% of Python3 online submissions for Count Good Nodes in Binary Tree.

Backlinks (1)

Coding Tests

Comments (0)