Day22-二叉树的迭代遍历

昨天学习了递归遍历：递归就是一次次的把参数压入栈中，然后返回的时候还是上一次递归保存的参数。

今天学习迭代遍历。

迭代遍历就是用栈去模拟保存二叉树的节点，然后依次去遍历，只不过要注意栈的后入先出的规则。

前序遍历：前序遍历的顺序应该是中左右，每次先处理中间节点，先把中间节点放入栈中，然后只要栈不为空就再调用一个指针去遍历二叉树，不过这个时候要注意：要先存放右节点，再存放左节点。

顺序应该是：12453 

迭代过程：

1. 栈初始化为 [1] → 弹出 1，记录 1，压入 3, 2（栈变为 [3, 2]）。

2. 弹出 2，记录 2，压入 5, 4（栈变为 [3, 5, 4]）。

3. 弹出 4，记录 4（无子节点，栈变为 [3, 5]）。

4. 弹出 5，记录 5（无子节点，栈变为 [3]）。

5. 弹出 3，记录 3（无子节点，栈为空）

代码实现：

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点，访问到最底层st.push(cur); // 将访问的节点放进栈cur = cur->left; // 左} else {cur = st.top(); // 从栈⾥弹出的数据，就是要处理的数据（放进result数组⾥的数据）st.pop();result.push_back(cur->val); // 中cur = cur->right; // 右}}return result;}
};

中序遍历：

这个不能直接修改前序遍历的代码：

迭代思路

1. 从根开始一路向左，把经过的节点全部压栈（不访问）。

2. 弹出栈顶，访问它（这就是“根”）。

3. 转向它的右子树，重复步骤1

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点，访问到最底层st.push(cur); // 将访问的节点放进栈cur = cur->left; // 左} else {cur = st.top(); // 从栈⾥弹出的数据，就是要处理的数据（放进result数组⾥的数据）st.pop();result.push_back(cur->val); // 中cur = cur->right; // 右}}return result;}
};

后序遍历：

这个和前序遍历基本上一样，只不过最后翻转一下数组就好了。