一、先序遍历

class Solution {
public:
void pre(TreeNode* root,vector<int>&p)
{
if(root!=nullptr)
{p.push_back(root->val);pre(root->left,p);pre(root->right,p);
}
}vector<int> preorderTraversal(TreeNode* root) {vector<int> p;pre(root,p);return p;}
};

二、先序非递归

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

 二、中序非递归

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

三、后序非递归:前序中左右子树入栈顺序稍作修改，将最后结果反转即可达到后序遍历

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