// OJ: https://leetcode.com/problems/binary-tree-preorder-traversal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if (!root) return {};
vector<int> ans;
stack<TreeNode*> s{{root}};
while (s.size()) {
root = s.top();
s.pop();
ans.push_back(root->val);
if (root->right) s.push(root->right);
if (root->left) s.push(root->left);
}
return ans;
}
};
// OJ: https://leetcode.com/problems/binary-tree-preorder-traversal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> s;
while (root || s.size()) {
if (!root) {
root = s.top();
s.pop();
}
ans.push_back(root->val);
if (root->right) s.push(root->right);
root = root->left;
}
return ans;
}
};
// OJ: https://leetcode.com/problems/binary-tree-inorder-traversal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> s;
while (root || s.size()) {
while (root) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
ans.push_back(root->val);
root = root->right;
}
return ans;
}
};
// OJ: https://leetcode.com/problems/binary-tree-postorder-traversal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> s;
TreeNode *prev = nullptr;
while (root || s.size()) {
while (root) {
s.push(root);
root = root->left;
}
root = s.top();
if (!root->right || root->right == prev) { // if root->right is nonexistent or visited, visit root
ans.push_back(root->val);
s.pop();
prev = root;
root = nullptr;
} else root = root->right; // otherwise, visit right subtree
}
return ans;
}
};
// OJ: https://leetcode.com/problems/binary-tree-level-order-traversal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
while (q.size()) {
int cnt = q.size();
ans.emplace_back();
while (cnt--) {
root = q.front();
q.pop();
ans.back().push_back(root->val);
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
}
}
return ans;
}
};