Count Univalue Subtrees

250. Count Univalue Subtrees

https://leetcode.com/problems/count-univalue-subtrees/

Account Login - LeetCode

 

language: C++

/**
 * 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 countUnivalSubtrees(TreeNode* root) {
        if(!root) return ret;
        if(isUnival(root, root->val)) ret++;
        countUnivalSubtrees(root->left);
        countUnivalSubtrees(root->right);
        return ret;
    }
private:     
    int ret;
    bool isUnival(TreeNode *root, int val){
        if(!root) return true;
        if(root->val == val)
        {
            bool local = isUnival(root->left, val) && isUnival(root->right, val);
            return local;
        }
        else
            return false;        
    }
};

 

내가 제출

/**
 * 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 countUnivalSubtrees(TreeNode* root) {
        if (!root) return 0;
        int sum = 0;
        helper(root, sum);
        return sum;
    }
    
    bool helper(TreeNode* current, int& sum) {
        if (current->left == nullptr && current->right == nullptr) {
            sum++;
            return true;
        }
        
        bool is_uni = true;
        
        if (current->left)
            is_uni = helper(current->left, sum) && is_uni && current->left->val == current->val;
        if(current->right) 
            is_uni = helper(current->right, sum) && is_uni && current->right->val == current->val;
        
        if(!is_uni) return false;
        sum++;
        return true;
    }
  
};

시도

/**
 * 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 countUnivalSubtrees(TreeNode* root) {
        if (!root) return 0;
        int sum = 0;
        helper(root, sum);
        return sum;
    }
    
    int helper(TreeNode* current, int& sum) {
        
        if (current->left) {
            if (helper(current->left, sum) == current->val)
                sum++;
        }
        if (current->right) {
            if (helper(current->right, sum) == current->val)
                sum++;
        }
        if (current->left == nullptr && current->right == nullptr) sum++;
        return current->val;
            
    }
};

 

문제점

univalue tree 가 무엇인지에 대한 이해가 부족했던 것 같다.

솔루션이 java, python 으로만 있어서 베스트한 c++ 해답은 아니고 위쪽 코드는 내가 그냥 맞춰서 짠건데

눈여겨봐야할 점은 bool 변수를 둬서 left, right child 와 현재 node 의 값이 다 같은지 확인한다는 점이다.

left, right child 의 값과 현재 node의 값이 같을 경우에 univalue subtree 가 되는 거고 또한 subtree 니까.. 

그래서 left, right  다 하나의 is_uni 라는 bool 변수 안에 넣었던 거고, 해당 변수가 필요한 이유였다. 

나는 그런 변수 없이 그저 leaf node 일 때, left right child 각각만 같은지만 검사했기 때문에 테스트 케이스를 통과하지 못했던 것.

 

주저리

이전에 풀었던 때는 프리미엄으로 결제한 것이 아니었기에 잠겨있는 부분(솔루션)이 있어서 

가장 최근에 풀었다고 적혀있던 문제와 솔루션 두 개를 보았다. 

문제 딱 보자마자 감도 안왔는데 dfs 사용하라는 discussioin 댓글들 보고 

흐릿하게 트리니까 체크해가면서 해보자 이런 식으로 생각해서 코드를 저런 식으로 짰고,

테스트 케이스가 제대로 안 되니까 아니 univalue subtree가 뭔소리야 하면서 솔루션을 봤다.

(어떨 때는 루트를 확인한 개수를 포함하고 어떨 때는 안 포함해서 <- 이게 서브트리 관련인 거였던 거지..)

근데 솔루션이 모든 언어가 아니라 java, python 으로만 되어있어서 나의 경우 엄청 베스트한 솔루션을 만들기보다 일단 흥미를 붙이고 꾸준히 풀어가는 게 목표이기 때문에.. 점차적으로 코드 질을 높이기는 해야되긴 할거다

discussion에도 막 사람들이 얘기해놓은 것 있어서 보다가도 시간이 많이 흐를 것 같았다.

첫날인데 하루 한 문제도 쉽지가 않다; 해졌으니까 산책하러 가야지..