class TrieNode
{
public:
// TrieNode 객체 생성
bool finish; //글자의 끝의 유/무 를 finish로 설정
TrieNode *children[26]; //26개의 자식 노드 생성 ('a~z')
TrieNode() //각 노드의 초기값 설정
{
finish = false;
for (int i = 0; i < 26; i++)
children[i] = NULL;
}//처음 아무것도 없는 상태이므로 각 노드의 끝을 false와 NULL로 설정
};
class WordDictionary {
public:
WordDictionary()
{
root = new TrieNode(); //Trie 생성
}
void addWord(string word)
{
int word_len = word.length(); //단어의 길이
int k = 0; //string -> int 알파벳 a~z 를 index로 사용하고자 k = 0~25 로 선언
TrieNode *cur = root; //탐색노드 cur에 초기 TrieNode 대입
for (int i = 0; i < word_len; i++) //단어의 한 글자씩 Trie 에 추가
{
k = word[i] - 'a';
if (cur->children[k] == NULL)
{
cur->children[k] = new TrieNode();
}////해당 trie가 아무것도 없는 상태라면, 새로 하위 노드 생성
cur = cur->children[k]; //다음 node로 이동
}
cur->finish = true; //단어의 끝 finish 값을 true로 설정
}
bool search(string word)
{
return searchHelper(word, root); //parameter를 수정한 search 함수
}
private:
TrieNode* root; //root 생성
bool searchHelper(string word, TrieNode* current)
{
for(int i = 0; i < word.size(); i++)
{
if(word[i] != '.'){ //기존 search 방식과 동일
if(!current->children[word[i] - 'a'])
return false;
current = current->children[word[i] - 'a'];
}
else
{ // '.'이 단어 중간에 있는 경우
for(int j = 0; j < 26; j++) // 다음 자식 노드 26개 모두를 탐색
{
if(current->children[j] && searchHelper(word.substr(i + 1), current->children[j]))
{ //다음 자식노드가 존재하고, 이후 다음 글자들이 Trie에 있는지 재귀로 탐색
return true; //하나라도 만족하면 true리턴
}
}
return false;
}
}
return current->finish; //'.'이 없는 경우 단어의 끝에 해당하는 Trie->finish 값 리턴
}
};
class TrieNode {
public:
// TrieNode 객체 생성
bool finish; //글자의 끝의 유/무 를 finish로 설정
TrieNode *children[26]; //26개의 자식 노드 생성 ('a~z')
TrieNode() //각 노드의 초기값 설정
{
finish = false;
for (int i = 0; i < 26; i++)
children[i] = NULL;
}//처음 아무것도 없는 상태이므로 각 노드의 끝을 false와 NULL로 설정
};
class Trie {
public:
Trie()
{
root = new TrieNode(); //Trie 생성
}
// 단어를 Trie에 Inserts
void insert(string word)
{
int word_len = word.length(); //단어의 길이
int k = 0; //string -> int 알파벳 a~z 를 index로 사용하고자 k = 0~25 로 선언
TrieNode *cur = root; //탐색노드 cur에 초기 TrieNode 대입
for (int i = 0; i < word_len; i++) //단어의 한 글자씩 Trie 에 추가
{
k = word[i] - 'a';
if (cur->children[k] == NULL)
{
cur->children[k] = new TrieNode();
}////해당 trie가 아무것도 없는 상태라면, 새로 하위 노드 생성
cur = cur->children[k]; //다음 node로 이동
}
cur->finish = true; //단어의 끝 finish 값을 true로 설정
}
//search 하는 단어가 Trie내에 있다면 true 없다면 false 리턴
bool search(string word)
{
int word_len = word.length();
int k = 0;
TrieNode *cur = root;
for (int i = 0; i < word_len; i++)
{
k = word[i] - 'a';
cur = cur->children[k];
if (cur == NULL)
return false;
}
return cur->finish;
//insert 글자의 끝 부분을 true로 했을 경우 true 리턴이고
//아닐 경우 defalut값이 false이므로 false리턴
}
//prefix를 가지는 글자가 있는지 탐색
bool startsWith(string prefix)
{
int word_len = prefix.length();
int k = 0;
TrieNode *cur = root;
for (int i = 0; i < word_len; i++)
{
k = prefix[i] - 'a';
cur = cur->children[k]; //찾는 단어의 글자 순으로 탐색
if (cur == NULL) //Trie가 NULL이거나,
//탐색할 다음 글자의 node가 NULL인 경우 false return
return false;
}
return true; //defalut 값 true
}
private:
TrieNode* root; //root 생성
};
class Solution {
public:
int kthSmallest(TreeNode* root, int& k)
{
if (root)
{
int x = kthSmallest(root->left, k);
return !k ? x : !--k ? root->val : kthSmallest(root->right, k);
}
else return NULL;
}
};
위 코드는 가독성이 떨어져 가독성이 좋은 코드를 찾아 해설해보았다.
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
return dfs(root, k);
}
int dfs(TreeNode* node, int& k) //int k 가 아니라 int& k 를 사용해 k값을 직접 변경한다.
{
if(!node) return NULL; //node가 없다면 null 리턴
int l = dfs(node->left,k); //BST 구조이므로 중위순회
if(k == 0) return l; //전달 받은 node->val 값 리턴, root로 다시 돌아올 때 k가 0인 상태가 된다.
else if(k == 1) //k가 1일 때의 값이 k번 째 값이므로
{
k--; //k를 0으로 만들고, 정답 리턴
return node->val;
}
else // k가 1보다 크면,
{
k--; //k를 1 줄이고 (탐색했다는 흔적)
int r = dfs(node->right,k); //오른쪽으로 중위순회를 이어나간다.
if(k==0) return r; //오른쪽 탐색결과 정답을 찾았으면 정답 값 리턴
else return NULL; //오른쪽이 빈노드거나 오른쪽을 탐색해도 못찾으면, null 리턴
}
}
};
class Solution {
vector<TreeNode*> nodes;
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if (!s && !t) return true; //둘다 null이면 true
if (!s || !t) return false; //하나만 null이면 false
getDepth(s, getDepth(t, -1)); //s의 깊이를 구하고, s의 깊이에 해당하는 node저장
for (TreeNode* n: nodes) //저장한 node들과 s가 같은지 확인
if (identical(n, t))
return true;
return false; //defalut 값 false
}
int getDepth(TreeNode* r, int d)
{
if (!r) return -1;
// -1인 이유 : 1. 가장 아래서부터 높이를 더하기 때문
//2. t에서 s와 높이가 같은 노드를 저장해야 하는 데,
// s의 높이를 구하는 과정에서 d가 0보다 클 경우,
// 저장 node에 s의 node가 들어가는 것을 막고자
int depth = max(getDepth(r->left, d), getDepth(r->right, d)) + 1;
//중위순회하며 높이 구하기
if (depth == d) //t-node 의 높이가 s의 높이와 같다면 해당 t-node 저장
nodes.push_back(r);
return depth;
}
bool identical(TreeNode* a, TreeNode* b)
{
if (!a && !b) return true; //둘다 null이면 true
if (!a || !b || a->val != b->val) return false;
//하나만 null이면 혹은 둘의 값이 다르면 false
return identical(a->left, b->left) && identical(a->right, b->right);
//false 가 하나라도 잡히면 false 리턴
}
};
class Solution {
public:
vector<vector<int>> ans; //정답 벡터
int max_depth = 0;
//resize가 줄어들게 되면, 기존 값들이 다 없어지기에, 최대 size를 유지해준다.
vector<vector<int>> levelOrder(TreeNode* root)
{
if(!root) return ans; //빈 트리면 null 리턴
ans.push_back(vector<int>()); //행 추가
ans[0].push_back(root->val); //root 값 추가
insert(root->left,1); //재귀로 깊이 탐색
insert(root->right,1);
return ans;
}
void insert(TreeNode* root, int c)
{
if(!root) return;
else
{
max_depth = c > max_depth? c : max_depth; //깊이가 늘어나면 최대 깊이 수정
ans.resize(max_depth+1); //최대 깊이에 맞게 size 수정한다.
ans[c].push_back(root->val); //레벨에 맞는 곳에 값 추가
insert(root->left,c+1);
insert(root->right,c+1);
}
}
};
New things learned
c++ resize를 사용시 size가 5였다가 3으로 다시 준다면, size가 5였을 때 값은 다 날라간다.
class Solution {
int sum;
public:
int maxPathSum(TreeNode* root)
{
sum = INT_MIN; //적어도 최소 하나는 더해야 하기에
//0이 아닌, 가장 작은 int값을 최소값으로 설정
help(root);
return sum;
}
int help(TreeNode* root)
{
if(!root) return 0; //재귀 탈출
int left = max(0,help(root->left)); //case 2
int right = max(0,help(root->right)); //case 3
sum = max(sum , left + right + root->val);
//case 1 : root와 left,right가 기존 sum 보다 크다면 셋의 합을 sum으로 한다.
return max(left,right) + root->val;
//case 4 left, right가 음수면, left와 right를 정하는 과정에서 l,r을 버린다.
}
};
