二叉树的遍历（非递归）

struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int a) : val(a), left(nullptr), right(nullptr){} };

二叉树的前序遍历（非递归）

vector<int> PreorderTravesal(TreeNode* root) { if (root == nullptr) { return{}; } vector<int> ans; stack<TreeNode*> stk; stk.push(root); while (!stk.empty()) { TreeNode* temp = stk.top(); stk.pop(); ans.push_back(temp->val); if (temp->right) { stk.push(temp->right); } if (temp->left) { stk.push(temp->left); } } return ans; }

二叉树的中序遍历（非递归）

vector<int> InorderTravesal(TreeNode* root) { if (root == nullptr) { return{}; } vector<int> ans; stack<TreeNode*> s; TreeNode* curNode = root; while (curNode || !s.empty()) { while (curNode) { s.push(curNode); curNode=curNode->left; } TreeNode* temp = s.top(); s.pop(); ans.push_back((temp->val); if (temp->right) { curNode = temp->right; } } return ans; }

二叉树的后序遍历（非递归）

vector<int> PostorderTraversal(TreeNode* root) { if (root == nullptr) { return{}; } vector<int> ans; stack<TreeNode*> s; s.push(root); while (!s.empty()) { TreeNode* temp = s.top(); s.pop(); ans.push_back(temp->val); if (temp->left) { s.push(temp->left); } if (temp->right) { s.push(temp->right); } } reverse(ans.begin(), ans.end()); return ans; }