leetcode 두 갈래 트리 비귀속 반복
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
if (root == NULL) return {};
vector res;
stack s;
s.push(root);
while(!s.empty())
{
TreeNode* top = s.top();
s.pop();
res.push_back(top->val);
if (top->right)
s.push(top->right);
if (top->left)
s.push(top->left);
}
return res;
}
};
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/(중순 반복)
class Solution {
public:
vector inorderTraversal(TreeNode* root) {
if (root == NULL) return {};
vector res;
stack s;
TreeNode* cur = root;
while(!s.empty() || cur != NULL)
{
if (cur != NULL)
{
s.push(cur);
cur = cur->left;
}
else
{
cur = s.top();
s.pop();
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
};
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/(뒷 순서 반복)
// ( -> -> , )
class Solution {
public:
vector postorderTraversal(TreeNode* root) {
if (root == NULL) return {};
vector res;
stack s;
s.push(root);
while(!s.empty())
{
TreeNode* top = s.top();
s.pop();
res.push_back(top->val);
if (top->left)
s.push(top->left);
if (top->right)
s.push(top->right);
}
reverse(res.begin(), res.end());
return res;
}
};
// ( )
class Solution {
public:
vector postorderTraversal(TreeNode* root) {
if (root == NULL) return {};
vector res;
stack s1;
stack s2;
s1.push(root);
while(!s1.empty())
{
TreeNode* top = s1.top();
s1.pop();
s2.push(top);
if (top->left)
s1.push(top->left);
if (top->right)
s1.push(top->right);
}
while(!s2.empty())
{
TreeNode* top = s2.top();
s2.pop();
res.push_back(top->val);
}
return res;
}
};
// ( , )
class Solution {
public:
vector postorderTraversal(TreeNode* root) {
if (root == NULL) return {};
vector res;
stack s;
TreeNode *cur = root;
TreeNode *last = NULL;
while(!s.empty() || cur)
{
if (cur)
{
s.push(cur);
cur = cur->left;
}
else
{
TreeNode *temp = s.top();
if (temp->right != NULL && temp->right != last)
{
cur = temp->right;
}
else
{
res.push_back(temp->val);
last = temp;
s.pop();
}
}
}
return res;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.