LeetCode 솔루션

[9/1] 1448. Count Good Nodes in Binary Tree

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.09.01 08:49

7,833 조회
2 댓글
0 추천
0 비추천
목록 게시글 쓰기

1448. Count Good Nodes in Binary Tree

Medium

3697109Add to ListShare

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.

Constraints:

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].

Accepted

241,765

Submissions

325,964

#Microsoft, #Salesforce

링크

https://leetcode.com/problems/count-good-nodes-in-binary-tree/ 1921 회 연결

익명
작성일 2022.09.01 08:49

Runtime: 576 ms, faster than 5.03% of Python3 online submissions for Count Good Nodes in Binary Tree.
Memory Usage: 32.4 MB, less than 87.02% of Python3 online submissions for Count Good Nodes in Binary Tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode, max_val = -1*10000) -> int:
        if not root: return 0
        
        ret_val = 1 if root.val >= max_val else 0
        
        return self.goodNodes(root.left, max(root.val, max_val)) + self.goodNodes(root.right, max(root.val, max_val)) + ret_val

익명
작성일 2022.09.05 16:05

Runtime: 325 ms, faster than 6.01% of C++ online submissions for Count Good Nodes in Binary Tree.
Memory Usage: 86.3 MB, less than 91.29% of C++ online submissions for Count Good Nodes in Binary Tree.

class Solution {
public:
    int ans = 1;
    void helper(TreeNode* node, int maximum) {
        if(!node)
            return;
        if(node->val >= maximum) {
            ans++;
            maximum = node->val;
        }
        helper(node->left, maximum);
        helper(node->right, maximum);
        return;
    }
    int goodNodes(TreeNode* root) {
        helper(root->left, root->val);
        helper(root->right, root->val);
        
        return ans;
    }
};