代码随想录算法训练营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

相关文章

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

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