整理一下二叉树的非递归遍历写法，什么时候忘了可以再看一下：
#include<iostream> #include <vector> #include <stack> #include <unordered_map> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; vector<int> pre{7, 6, 4, 3, 5, 2, 1}; vector<int> in{4, 6, 3, 7, 2, 5, 1}; // 根据前序和中序创建二叉树 TreeNode* createTree(vector<int>& pre, vector<int>& in, int preSt, int preEd, int inSt, int inEd) { if (preSt > preEd) return nullptr; TreeNode* root = new TreeNode(pre[preSt]); int index = inSt; for (; index <= inEd; ++index) { if (in[index] == pre[preSt]) break; } root->left = createTree(pre, in, preSt + 1, preSt + index - inSt, inSt, index - 1); root->right = createTree(pre, in, preSt + index - inSt + 1, preEd, index + 1, inEd); return root; } // 前序非递归遍历 void preOrder(TreeNode* root, vector<int>& num) { stack<TreeNode*> st; TreeNode* p = root; while (p || !st.empty()) { while (p) { num.push_back(p->val); st.push(p); p = p->left; } if (!st.empty()) { p = st.top(); st.pop(); p = p->right; } } } // 中序非递归遍历 void inOrder(TreeNode* root, vector<int>& num) { stack<TreeNode*> st; TreeNode* p = root; while (p || !st.empty()) { while (p) { st.push(p); p = p->left; } p = st.top(); num.push_back(p->val); st.pop(); p = p->right; } } // 后序非递归遍历 void postOrder(TreeNode* root, vector<int>& num) { stack<TreeNode*> st; TreeNode* p = root; TreeNode* temp; unordered_map<TreeNode*, bool> mp; while (p || !st.empty()) { while (p) { mp[p] = true; st.push(p); p = p->left; } temp = st.top(); st.pop(); if (mp[temp]) { mp[temp] = false; st.push(temp); p = temp->right; } else { num.push_back(temp->val); p = nullptr; } } } void showOrder(vector<int>& vec) { for (int i = 0; i < vec.size(); ++i) { cout << vec[i] << " "; } cout << endl; } int main() { TreeNode* root = createTree(pre, in, 0, 6, 0, 6); vector<int> preNum, inNum, postNum; preOrder(root, preNum); inOrder(root, inNum); postOrder(root, postNum); showOrder(preNum); showOrder(inNum); showOrder(postNum); return 0; }