엔지니어 게시판
LeetCode 솔루션 분류

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

컨텐츠 정보

본문

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

관련자료

댓글 2

학부유학생님의 댓글

  • 익명
  • 작성일
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

재민재민님의 댓글

  • 익명
  • 작성일
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;
    }
};
전체 396 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 131 명
  • 오늘 방문자 1,527 명
  • 어제 방문자 6,462 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,049 명
알림 0