从零开始的LeetCode刷题日记：二叉树的迭代遍历

一.相关链接

题目链接：

144. 二叉树的前序遍历

145.二叉树的后序遍历

94.二叉树的中序遍历

二.心得体会

前面用简单的递归法几行实现了这些问题，有些题目可以用迭代法来实现，通常使用的辅助数据结构是栈（递归的底层逻辑就是栈）。

1.对于前序遍历来说，整体的方法比较简单，在弹出节点的时候，只需要把该节点的右节点和左节点依次弹进栈即可（因为栈是先进后出）。

2.后序遍历相对来说比较简单，目前知道前序遍历是中左右，那么我们改变左右子树的遍历顺序就成了中右左，然后整体翻转就变成了后序遍历的左右中了！

3.对于中序遍历来说，因为它的遍历顺序和访问顺序不一样，所以和前序、中序不一样。那么我们就要首先一路往最左下角找到第一个节点。一直到访问到空节点的时候，代表我们找到了最左边的节点，那么就可以开始访问这个节点，并回溯到它的父节点访问父节点，接下来就是往右子树访问了。

三.代码

1.前序遍历的迭代法实现：

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

2.后续遍历的迭代法实现：

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

3.中序遍历的迭代法实现：

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