南大得模板,感觉不错
前序遍历
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
auto cur = root;
while (stk.size() || cur) {
while (cur) {
res.push_back(cur->val);
stk.push(cur);
cur = cur->left;
}
if (stk.size()) {
auto t = stk.top();
stk.pop();
cur = t->right;
}
}
return res;
}
中序遍历
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
auto cur = root;
while (stk.size() || cur) {
while (cur) { // 循环往左走
stk.push(cur);
cur = cur->left;
}
if (stk.size()) {
auto t = stk.top();
stk.pop();
res.push_back(cur->val);
cur = t->right;
}
}
return res;
}
后序遍历
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
auto cur = root;
while (stk.size() || cur) {
while (cur) {
stk.push(cur);
res.insert(res.begin(), cur->val); // 对比前序遍历,倒着插即可
cur = cur->right;
}
if (stk.size()) {
auto t = stk.top();
stk.pop();
cur = t->left;
}
}
return res;
}