Leetcode의 두 갈래 나무가 두루 총결되다
47304 단어 Leetcode
1. Leetcode 144를 앞뒤로 훑어본다.Binary Tree Preorder Traversal
/*
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if( root == NULL )
return res;
__preorderTraversal(root, res);
return res;
}
private:
void __preorderTraversal(TreeNode* node, vector<int>& res){
if( node == NULL )
return;
res.push_back(node->val);
__preorderTraversal(node->left, res);
__preorderTraversal(node->right, res);
return;
}
};
//
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(root == NULL)
return res;
stack<TreeNode*> stack;
TreeNode* cur = root;
while(cur != NULL || !stack.empty()){
while(cur != NULL){
res.push_back(cur->val);
stack.push(cur);
cur = cur->left;
}
cur = stack.top();
stack.pop();
cur = cur->right;
}
return res;
}
};
2. Leetcode 94를 반복합니다.Binary Tree Inorder Traversal
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if(root == NULL)
return res;
__inorderTraversal(root, res);
return res;
}
private:
void __inorderTraversal(TreeNode* node, vector<int>& res){
if(node == NULL)
return;
__inorderTraversal(node->left, res);
res.push_back(node->val);
__inorderTraversal(node->right, res);
return;
}
};
//
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if( root == NULL )
return res;
stack<TreeNode*> stack;
TreeNode* cur = root;
while( cur != NULL || !stack.empty() ){
while( cur != NULL ){
stack.push( cur );
cur = cur->left;
}
cur = stack.top();
stack.pop();
res.push_back( cur->val );
cur = cur->right;
}
return res;
}
};
3. Leetcode 145를 뒤돌아본다.Binary Tree Postorder Traversal
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if( root == NULL )
return res;
__postorderTraversal(root, res);
return res;
}
private:
void __postorderTraversal(TreeNode* node, vector<int>& res){
if( node == NULL )
return;
__postorderTraversal(node->left, res);
__postorderTraversal(node->right, res);
res.push_back( node->val );
return;
}
};
//
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if( root == NULL )
return res;
stack<TreeNode*> stack;
TreeNode* pre = NULL;
TreeNode* cur = root;
while( cur != NULL || !stack.empty() ){
while( cur != NULL ){
stack.push( cur );
cur = cur->left;
}
cur = stack.top();
stack.pop();
if( cur->right == NULL || pre == cur->right ){
res.push_back( cur->val );
pre = cur;
cur = NULL;
}
else{
stack.push(cur);
cur = cur->right;
}
}
return res;
}
};
4. 층차가 102번을 반복한다.Binary Tree Level Order Traversal
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == NULL)
return res;
queue<TreeNode*> q;
q.push(root);
int level_num = 1;
while( !q.empty() ){
int new_level_num = 0;
vector<int> level;
for(int i = 0; i < level_num; i++){
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if(node->left){
q.push(node->left);
new_level_num++;
}
if(node->right){
q.push(node->right);
new_level_num++;
}
}
res.push_back(level);
level_num = new_level_num;
}
return res;
}
};
층차는 두 가지 변체가 있는데 그것이 바로 우시수와 지자수이다.우시수는 바로 한 그루의 나무 오른쪽에 서 있는 아이입니다. 보는 아이입니다. 생각: 처음부터 생각한 것은 층층이 차례대로 하는 것입니다. 그런데 어떻게 층층이 가장 오른쪽에 있는 아이를 얻을 수 있을까요?당시 102를 참고하여 한 층마다vector로 저장하고 for순환을 통해 매번 마지막 값을 찾으면 된다고 생각했지만 좀 귀찮아서 손을 대지 않았다.뒤에 스택으로 저장하는 것을 발견하면 뒤에 바로 top () 가 훨씬 간단해진다.
우시수 Leetcode 199.Binary Tree Right Side View를 102에서 바로 vector를 stack으로 바꿨습니다.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if(root == NULL)
return res;
queue<TreeNode*> q;
q.push(root);
int level_num = 1;
while( !q.empty() ){
int new_level_num = 0;
stack<int> level;
for(int i = 0; i < level_num; i++){
TreeNode* node = q.front();
q.pop();
level.push(node->val);
if(node->left){
q.push(node->left);
new_level_num++;
}
if(node->right){
q.push(node->right);
new_level_num++;
}
}
res.push_back( level.top() );
level_num = new_level_num;
}
return res;
}
};
Leetcode 103.Binary Tree Zigzag Level Order Traversal은 보조 창고 2개가 필요합니다.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == NULL)
return res;
stack<TreeNode*> levels[2];
int cur = 0;
int next = 1;
levels[cur].push(root);
while( !levels[cur].empty() || !levels[next].empty() ){
vector<int> temp;
while( !levels[cur].empty() ){
TreeNode* node = levels[cur].top();
levels[cur].pop();
temp.push_back(node->val);
if(cur == 0){
if(node->left)
levels[next].push(node->left);
if(node->right)
levels[next].push(node->right);
}
else{
if(node->right)
levels[next].push(node->right);
if(node->left)
levels[next].push(node->left);
}
}
res.push_back(temp);
if( levels[cur].empty() ){
cur = 1 - cur;
next = 1- next;
}
}
return res;
}
};
ps:1.검지offer의 제목은 정말 너무 고전적이어서 두껍게 읽어야 한다. 한 번에 완전무결하게 만들 생각은 하지 마라. 이것은 불가능하다. 한 번 더 읽으면 자연히 한 번 더 읽을 수 있다는 깨달음이 생긴다.2. 보보 선생님 Leetcode 문제풀이,https://github.com/liuyubobobo/Play-Leetcode정말 회색으로 잘 썼어요. 닭으로서도 보보 선생님을 베낄 수밖에 없었어요.마지막으로 자신에게 한마디, 파이팅 오리!!!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
