栈模拟先序后序中序遍历（非递归遍历）

先序遍历：

vector<int> preorderTraversal(TreeNode* u) {stack<TreeNode*>stk;vector<int>res;if(u==nullptr) return res;while(stk.size()||u){if(u){res.push_back(u->val);//遍历当前结点stk.push(u);//记录当前递归层u=u->left;//遍历左子树}else {u=stk.top();stk.pop();//返回上一层递归层u=u->right;//遍历右子树}}return res;}

优化版：

vector<int> preorderTraversal(TreeNode* u) {stack<TreeNode*>stk;vector<int>res;if(u==nullptr) return res;stk.push(u);while(stk.size()){auto t=stk.top();stk.pop();res.push_back(t->val);if(t->right)stk.push(t->right);//后遍历的先入栈，即右子树先入栈if(t->left)stk.push(t->left);//先遍历的后入栈，即左子树后入栈}return res;}

后序遍历：

后序遍历与先序遍历有互通之处，即后序遍历的倒序为：根右左。

所以我们可以把先序遍历的左右子树的遍历顺序倒一下便变成了后序遍历的倒序。

vector<int> postorderTraversal(TreeNode* u) {stack<TreeNode*>stk;vector<int>res;if(u==nullptr) return res;while(stk.size()||u){if(u){res.push_back(u->val);//遍历当前结点stk.push(u);//记录下该层的遍历u=u->right;//先遍历右子树}else {u=stk.top();stk.pop();u=u->left;//再遍历左子树}}reverse(res.begin(),res.end());return res;}

同样有优化版：

vector<int> postorderTraversal(TreeNode* u) {stack<TreeNode*>stk;vector<int>res;if(u==nullptr) return res;stk.push(u);while(stk.size()){TreeNode* t=stk.top();stk.pop();res.push_back(t->val);if(t->left)stk.push(t->left);if(t->right)stk.push(t->right);}reverse(res.begin(),res.end());return res;}

中序遍历：

vector<int> inorderTraversal(TreeNode* root) {vector<int>res;stack<TreeNode*>stk;while(stk.size()||root){if(root){stk.push(root);//相当于记录下了当前层递归root=root->left;//先遍历左子树}else{root=stk.top();//返回上一层递归stk.pop();res.push_back(root);//遍历当前结点root=root->right;//遍历右子树}}return res;}

中序遍历没有找到优化版，，