Count Good Nodes in Binary Tree[Tree,Depth-First Search,Breadth-First Search,Binary Tree]

https://leetcode.com/problems/count-good-nodes-in-binary-tree/

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

사람들은 쉽다는데, 이게 어디가 쉬운건지 참!

 

1. C

solution을 너무 쉽게 쉽게 보는 거 같다.

머리가 굳어서 그런가..

경계하자.. 주기적으로 코딩문제를 풀면서 연습량을 늘려야 한다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int goodNodes(struct TreeNode* root){
    if(!root) return 0;
    int cnt = 0;
    void dfs(struct TreeNode* node, int curMax){
        if(!node) return;
        if(node->val >= curMax){
            cnt++;
            curMax = node->val;
        }
        dfs(node->left,curMax);
        dfs(node->right,curMax);
    }
    dfs(root,root->val);
    return cnt;
}

 

2. C++

이번엔 Stack을 써서 풀어본 문제다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int goodNodes(TreeNode* root) {
        if(!root) return 0;
        int cnt = 0;
        stack<pair<TreeNode*, int>> s;
        s.push({root,root->val});
        
        while(!s.empty()){
            auto [node, max_val] = s.top();
            s.pop();
            if(node->val >= max_val){
                cnt++;
                max_val = node->val;
            }
            // int new_max = max(max_val,node->val);
            if(node->left){
                s.push({node->left,max_val});
            }
            if(node->right){
                s.push({node->right,max_val});                
            }
        }
        return cnt;
    }
};

 

3. Python

 

하나 특이한건, C에서는 그냥 int cnt가 내부 재귀함수에 의해서 자연스럽게 +1씩 되었는데,

Python에선 list구조로 써줘야지 주소값?을 받아서 변경이 가능한가보다..

# 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) -> int:
        if not root : return 0
        cnt = [0]
        def dfs(node,maxval):
            if not node : return    
            if node.val >= maxval :
                maxval = node.val
                cnt[0] += 1
            dfs(node.left,maxval)
            dfs(node.right,maxval)

        dfs(root,root.val)
        return cnt[0]

왜 int로 하면 안 되는가? 파이썬의 변수 범위(scope) 문제: 파이썬에서는 함수 내부에서 외부 변수를 참조할 수는 있지만, 그 값을 직접 변경할 수는 없습니다. 함수 내부에서 정수형 변수(int)를 수정하면, 파이썬은 이를 새로운 지역 변수로 간주합니다. 재귀 호출에서 cnt를 수정하려 하면, 각 호출마다 cnt는 새로운 지역 변수로 취급되어 호출 사이의 값을 공유하지 않습니다. int는 불변 객체(immutable): int는 불변 객체이기 때문에, 값이 변경되면 새로운 객체가 생성됩니다. 따라서 재귀 함수 내부에서 int 변수를 증가시키는 방식은 원래의 변수를 수정하지 않습니다.