面试题：二叉树的非递归先序遍历，非递归中序遍历，非递归后序遍历

非递归先序遍历，非递归中序遍历，非递归后序遍历都是借助栈来完成的

非递归先序遍历

思路 因为需要借助栈，栈是先进后出的数据结构，所以,需要先将右节点进行入栈，然后再将左节点进行入栈，出栈时，出栈顶（左节点） 代码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> ret_v; if(root==nullptr) { return ret_v; } stack<TreeNode *> s; s.push(root); while(!s.empty()) { TreeNode* tempt_root=s.top(); ret_v.push_back(tempt_root->val); s.pop(); if(tempt_root->right!=nullptr) { s.push(tempt_root->right); } if(tempt_root->left!=nullptr) { s.push(tempt_root->left); } } return ret_v; } };

非递归中序遍历 思路 我们需要注意，中序遍历是左右根，需要保持首先左，证明需要一直找左边（没有找到做节点的末尾一直入栈），直到左边为null,将左节点弹出（栈顶），然后看有没有右节点，没有的话，继续弹出栈顶，有右节点的话，先将右节点入栈，然后一直找左节点…

代码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> ret_v; if(root==nullptr) { return ret_v; } stack<TreeNode *> s; while(s.empty()==false||root!=nullptr) { while(root!=nullptr) { s.push(root); root=root->left; } //这里当然可以将 TreeNode* tempt_node 换成是 root（后面tempt_node全都用root代替） TreeNode* tempt_node=s.top(); ret_v.push_back(tempt_node->val); s.pop(); root=tempt_node->right;//注意这里可以直接这样，与前序后序不同 } return ret_v; } };

非递归后序遍历 思路 我们其实后序遍历和前序遍历是有关系的 先序遍历：root,left,right 后序遍历：left ,right,toot

root,left,right==>root,right,left==>left ,right,toot 具体操作如下 root,left,right==>root,right,left（栈先压左后压右节点，栈顶就是右节点）==>left ,right,toot（将最终的结果ret_v进行逆序，也就是reverse）

代码如下：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> ret_v; if(root==nullptr) { return ret_v; } stack<TreeNode *> s; s.push(root); while(s.empty()==false) { TreeNode*temp_node= s.top(); ret_v.push_back(temp_node->val); s.pop(); if(temp_node->left) { s.push(temp_node->left); } if(temp_node->right) { s.push(temp_node->right); } } reverse(ret_v.begin(),ret_v.end()); return ret_v; } };