代码随想录算法训练营DAY14|C++二叉树Part.1|二叉树的递归遍历、二叉树的迭代遍历、二叉树的统一迭代法

本文主要是介绍代码随想录算法训练营DAY14|C++二叉树Part.1|二叉树的递归遍历、二叉树的迭代遍历、二叉树的统一迭代法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 二叉树的递归遍历
    • 思路
    • CPP代码
  • 二叉树的迭代遍历
    • 思路
      • 前序遍历
      • 后序遍历
      • 后序遍历
  • 二叉树的统一迭代法

二叉树的递归遍历

144.二叉树的前序遍历、145.二叉树的后序遍历、94.二叉树的中序遍历

文章讲解:二叉树的递归遍历

视频讲解:每次写递归都要靠直觉? 这次带你学透二叉树的递归遍历!

状态:搞清楚本题就一定要先搞清楚递归是什么,曾经可能需要靠栈来想想递归的工作流程,现在我觉得树结构就很好得向我们展示了递归这个方法。

思路

首先搞清楚前中后序的遍历方法,这里以前序遍历进行举例。

20200806191109896

如果用递归的思路来思考前序遍历,其实就是每到一个结点,我们就对其先进性处理,然后分别去遍历左、右孩子。

要写明白递归,就要有三大要素:

  • 确定递归的参数和返回值:这里我们遍历到结点处,通过数组进行存储,所以返回值是void,数组作为参数传进来即可:
void traversal(TreeNode* cur, vector<int> res){...
}
  • 确定终止条件:在递归的过程中,如何算是递归结束了呢,当然是当前遍历的节点是空了,那么本层递归就要结束了,所以如果当前遍历的这个节点是空,就直接return,代码如下:
if (cur == NULL) return;
  • 确定单层递归的逻辑:前序遍历是中左右的循序,所以在单层递归的逻辑,是要先取中节点的数值,代码如下:
vec.push_back(cur->val);    // 中
traversal(cur->left, vec);  // 左
traversal(cur->right, vec); // 右

剩下的中序遍历、后序遍历只要把遍历顺序换个位置即可:

//中序
traversal(cur->left, vec);  // 左
vec.push_back(cur->val);    // 中
traversal(cur->right, vec); // 右//后序
traversal(cur->left, vec);  // 左
traversal(cur->right, vec); // 右
vec.push_back(cur->val);    // 中

CPP代码

//前序遍历
class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val);    // 中traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

二叉树的迭代遍历

144.二叉树的前序遍历、145.二叉树的后序遍历、94.二叉树的中序遍历

文章讲解:二叉树的迭代遍历

视频讲解:写出二叉树的非递归遍历很难么?(前序和后序)写出二叉树的非递归遍历很难么?(中序))

状态:迭代中的第一步没处理好,一直在想我怎么在迭代中让结点遍历起来呢?本质就是栈里面存储的其实不是结点数值,而是把整个结点都存储进去了。

迭代遍历总结两点:栈内存储的是结点,这样才知道如何结点是如何遍历起来的;把结点存储在栈的核心就是,只要不处理,就不应该弹出,处理的时候才弹出

思路

这篇文章已经把思路解释的非常清楚了:二叉树的递归遍历、二叉树的迭代遍历、二叉树的统一迭代法

前序遍历

  • 搞清楚栈内到底存的是值还是结点:存储结点,如果存储值的话,我们没有手段去遍历二叉树了

记得提前存入根结点,如果没有根结点,直接返回空。

  • 搞清楚循环体内如何去遍历整个二叉树:

同第三点的强调,栈顶元素是哪一个,我们才遍历哪一个

  • 搞清楚在模拟出栈入栈过程中,我们关注的其实是栈顶结点,栈顶结点跑到哪里,我们就遍历哪个子树。
TreeNode* node = st.top();
st.pop();
if(node->right) st.push(node->right);
if(node->left) st.push(node->left);

整体代码如下:

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top();                       // 中st.pop();result.push_back(node->val);if (node->right) st.push(node->right);           // 右(空节点不入栈)if (node->left) st.push(node->left);             // 左(空节点不入栈)}return result;}
};

后序遍历

前序遍历是中左右-----(调整代码左右循环)---->中右左----(反转result数组)---->左右中

我们的后序遍历就是左右中!所以前序遍历的代码很重要!

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top();                       // 中st.pop();result.push_back(node->val);if (node->left) st.push(node->left);             // 左(空节点不入栈)if (node->right) st.push(node->right);           // 右(空节点不入栈)}reverse(result.begin(), result.end());return result;}
};

后序遍历

后序遍历最难的点就在于,我们遍历的结点不是我们要处理的结点,我们遍历过该结点后可能要到后面才能去处理,这样应该怎么办呢?一个办法:借助指针

我们用指针来遍历整个二叉树,然后用栈来存储遍历的顺序

再进一步,中序遍历的规矩就是,左孩子不是空,左孩子压栈,如果空了(左),就要处理栈顶元素(中),然后压入右孩子,如果右孩子是空,那就继续处理栈顶元素和栈顶的右孩子(右)。

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<int> st;vector<int> result;TreeNode* cur = root;while(cur != NULL|| !st.empty()){	//0 1 则 1	if(cur != NULL){st.push(cur);cur = cur->left;}else{cur = st.top();st.pop();result.push_bacl(cur->val);cur->right;}}return result;}
};

二叉树的统一迭代法

文章讲解:二叉树的统一迭代法

状态:感觉有点厉害,以后有时间在进行研究。

这篇关于代码随想录算法训练营DAY14|C++二叉树Part.1|二叉树的递归遍历、二叉树的迭代遍历、二叉树的统一迭代法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/870661

相关文章

Java设计模式---迭代器模式(Iterator)解读

《Java设计模式---迭代器模式(Iterator)解读》:本文主要介绍Java设计模式---迭代器模式(Iterator),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录1、迭代器(Iterator)1.1、结构1.2、常用方法1.3、本质1、解耦集合与遍历逻辑2、统一

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多,因为它实际属于c++20最为重要的

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN