使用栈实现二叉树的前中后序遍历

前序：

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {if(root==NULL) return {};stack<TreeNode*> s;s.push(root);vector<int> ans;while(!s.empty()){TreeNode* tmp = s.top();s.pop();ans.push_back(tmp->val);if(tmp->right) s.push(tmp->right);if(tmp->left) s.push(tmp->left);}return ans;}
};

中序

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;stack<TreeNode*> s;TreeNode* tmp;tmp = root;while(tmp!=NULL || !s.empty()){while(tmp){s.push(tmp);tmp = tmp->left;}tmp = s.top();s.pop();ans.push_back(tmp->val);tmp = tmp->right;}return ans;}
};

后序

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {if(root==NULL) return {};stack<TreeNode*> s;s.push(root);vector<int> ans;TreeNode* tmp;while(!s.empty()){tmp = s.top();s.pop();ans.push_back(tmp->val);if(tmp->left) s.push(tmp->left);if(tmp->right) s.push(tmp->right);}reverse(ans.begin(),ans.end());return ans;}
};