#include <stdio.h> #include <vector> #include <stack> #include <string> struct node { int val; node *left, *right; node(int val) : val(val), left(nullptr), right(nullptr) {} }; //先序遍历,中左右 std::vector<int> pre_order_traverse(node *root) { std::vector<int> ans; std::stack<node *> s; node *p = root; while (p || !s.empty()) { if (!p) { p = s.top(); s.pop(); } else { ans.push_back(p->val); if (p->right) s.push(p->right); p = p->left; } } return ans; } //中序遍历,左中右 std::vector<int> in_order_traverse(node *root) { std::vector<int> ans; std::stack<node *> s; node *p = root; while (p || !s.empty()) { if (!p) { p = s.top(); ans.push_back(p->val); p = p->right; s.pop(); } else { s.push(p); p = p->left; } } return ans; } //后序遍历,左右中 std::vector<int> post_order_traverse(node *root) { //先中右左然后反序 std::vector<int> reversed_ans; std::stack<node *> s; node *p = root; while (p || !s.empty()) { if (!p) { p = s.top(); s.pop(); } else { reversed_ans.push_back(p->val); if (p->left) s.push(p->left); p = p->right; } } return std::vector<int>(reversed_ans.rbegin(), reversed_ans.rend()); } struct foo { int val; foo(int val) : val(val) {} }; foo f() { return foo(50); } int main() { node *root = new node(1); root->left = new node(3); root->right = new node(2); root->left->left = new node(4); root->left->right = new node(5); std::vector<int> ans = post_order_traverse(root); for (int temp : ans) printf("%d ", temp); return 0; }