代码随想录day12 | [前、中、后、层]二叉树的遍历迭代法和递归法

文章目录

- 一、前后中序递归法
- 二、前后序迭代法
- 三、中序遍历迭代法
- 四、层序遍历

递归三部曲：
1️⃣ 第一步确定递归函数的返回值和参数
2️⃣第二步确定递归的终止条件
3️⃣第三步确定单层递归处理的逻辑

一、前后中序递归法

前序遍历二叉树

class Solution
{
private:vector<int> res;public:void dfs(TreeNode *root){if (root == nullptr)return;res.push_back(root->val);if (root->left)preorderTraversal(root->left);if (root->right)preorderTraversal(root->right);}vector<int> preorderTraversal(TreeNode *root){dfs(root);return res;}
};

二、前后序迭代法

前序遍历二叉树
借助栈来实现。
在这里插入图片描述

按理说应该是：根左右
但是是栈的结构，所以入孩子节点的时候，先右再左。
这样方便弹出！
在这里插入图片描述

前序遍历非递归：
class Solution
{
public:vector<int> preorderTraversal(TreeNode *root){// 迭代法vector<int> res;stack<TreeNode *> st;if (root == nullptr)return res;st.push(root);while (!st.empty()){// 每次进入循环需要先获得栈顶元素TreeNode *tmp = st.top(); // 根st.pop();res.push_back(tmp->val);if (tmp->right)st.push(tmp->right); // 右if (tmp->left)st.push(tmp->left); // 左}return res;}
};

前序遍历改为后序遍历只需要改2行，再加一行即可。
右左换一下顺序，再逆置一下res数组即可得到我们的答案。

后序遍历非递归：
class Solution
{
public:vector<int> preorderTraversal(TreeNode *root){// 迭代法vector<int> res;stack<TreeNode *> st;if (root == nullptr)return res;st.push(root);while (!st.empty()){// 每次进入循环需要先获得栈顶元素TreeNode *tmp = st.top(); // 根st.pop();res.push_back(tmp->val);if (tmp->left)st.push(tmp->left); // 左if (tmp->right)st.push(tmp->right); // 右}reverse(res.begin(),res.end());return res;}
};

三、中序遍历迭代法

94.二叉树的中序遍历

为何中序遍历的非递归不同？

因为访问处理的顺序和遍历的顺序是不同的。
所以我们需要一个指针来帮助我们遍历二叉树，使用栈来处理节点上的元素。

// 中序遍历使用迭代法
class Solution
{
public:vector<int> inorderTraversal(TreeNode *root){// 迭代法vector<int> res;stack<TreeNode *> st;TreeNode *cur = root;while (cur != nullptr || !st.empty()){if (cur != nullptr){st.push(cur);cur = cur->left; // 左}else{// cur==nullptr 那么把cur指向栈顶元素岂不是更方便迭代？cur = st.top();st.pop();res.push_back(cur->val); // 根cur = cur->right;        // 右}}return res;}
};

四、层序遍历

102.二叉树的层序遍历
要使用队列。

class Solution
{
public:vector<vector<int>> levelOrder(TreeNode *root){vector<vector<int>> res;queue<TreeNode *> q;if (root != nullptr)q.push(root);while (!q.empty()){int size = q.size();vector<int> v;for (int i = 0; i < size; i++){// 每次进入循环，都需要一个迭代变量TreeNode *tmp = q.front();q.pop(); // 每次弹出的元素就是要记录到数组的元素v.push_back(tmp->val);// 将左右孩子 加入队列if (tmp->left)q.push(tmp->left);if (tmp->right)q.push(tmp->right);}res.push_back(v);}return res;}
};