当前位置：首页 > news >正文

二叉树的遍历【C++】

news 2024/9/21 2:44:22

对于二叉树系列的题，必须要会遍历二叉树。
遍历的有：深度优先：前序、中序、后序，广度优先：层序遍历
什么序是指处理根节点在哪个位置，比如前序是指处理节点顺序：根左右。
接下来要说明的是：选用递归实现还是迭代实现，一般来说递归法和迭代法可以相互转化。
递归有固定的流程：

递归函数的参数和返回值
终止条件
单层递归的逻辑

递归顺序分为：

访问顺序：都是根左右
处理顺序：和什么序一致，和题目描述有关，这是二叉树题目的关键

迭代常常使用栈或者队列来实现

题目链接：
二叉树的前序遍历
二叉树的中序遍历
二叉树的后序遍历
二叉树的层序遍历
那么这4种遍历顺序和2种实现方式就有4 * 2 == 8种代码实现：

递归前序

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;   //存放结果preorder(root, res);   //递归调用return res;}void preorder(TreeNode* root, vector<int>& res) {  //1.递归函数的参数和返回值if (root == nullptr) {   //2.终止条件return;}res.push_back(root -> val);   //3.单层递归的逻辑preorder(root -> left, res);  //根左右preorder(root -> right, res);}
};

递归中序

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

递归后序

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

可以看出：递归法的前中后序的区别在于处理根节点的顺序不同。

迭代前序

使用代码随想录的图片：
在这里插入图片描述
注意：栈是先入后出，所以要先放入右节点。

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;if (root == nullptr) {   //边界判断return res;}stack<TreeNode*> stk;stk.push(root);while (!stk.empty()) {TreeNode* cur = stk.top();stk.pop();res.push_back(cur -> val);if (cur -> right) {    //关键stk.push(cur -> right);}if (cur -> left) {stk.push(cur -> left);}}return res;}
};

迭代中序

代码随想录的图片：
在这里插入图片描述

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;}
};

迭代后序：

在这里插入图片描述
由上图可知：只需要将先序遍历调整左右顺序，并反转结果数组，就能得到后序遍历。

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> stk;if (root == nullptr) {return res;}stk.push(root);while (!stk.empty()) {TreeNode* node = stk.top();stk.pop();res.push_back(node -> val);if (node -> left) stk.push(node -> left);  //和先序区别if (node -> right) stk.push(node -> right);}reverse(res.begin(), res.end());   //反转结果return res;}
};

递归层序

访问顺序：根左右
处理顺序：使用一个depth变量，记录当前在哪一层

class Solution {
public:void order(TreeNode* cur, vector<vector<int>>& result, int depth){if (cur == nullptr) return;if (result.size() == depth) result.push_back(vector<int>());result[depth].push_back(cur->val);  //放入对应层order(cur->left, result, depth + 1);order(cur->right, result, depth + 1);}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;}
};

迭代层序

代码随想录的动态图如下：
在这里插入图片描述

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;   //队列实现if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;}
};