【夜深人静学数据结构与算法 | 第四篇】手撕二叉树遍历

这篇具有很好参考价值的文章主要介绍了【夜深人静学数据结构与算法 | 第四篇】手撕二叉树遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言:

二叉树遍历方式:

手撕前中后序遍历(递归)的三大准备

深度优先搜索: 

手撕前中后遍历(递归):

手撕前中后序遍历(迭代):

深度优先搜索:

总结:


前言:

        今天我们将带领大家手撕二叉树的遍历,本篇会分别讲解深度优先搜索法和广度优先有搜索法下的各自详细算法,大家做好准备了嘛?

二叉树遍历方式:

  • 深度优先遍历
  • 广度优先遍历

手撕前中后序遍历(递归)的三大准备

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

深度优先搜索: 

手撕前中后遍历(递归):

【夜深人静学数据结构与算法 | 第四篇】手撕二叉树遍历

        讲深度优先搜索遍历,实际上就是在讲前中后序遍历的方法,我们先用前序遍历进行讲解。 

1.确定递归函数的参数和返回值:我们就只传递一个节点以及存储遍历结果用的vector容器就可以了。

void traversal(TreeNode* cur, vector<int>& vec)

2.确定终止条件:在递归的时候,如果下层没有节点,那么就证明我们此时已经遍历到最底层了,就要返回,也就是如果这个节点为空节点,我们就要终止递归。

if (cur == NULL) return;

3.确定单层递归的逻辑:前序遍历是中左右的循序,所以在单层递归的逻辑,是要先取中节点的数值,代码如下:

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

单层递归的逻辑就是按照中左右的顺序来处理的,这样二叉树的前序遍历,基本就写完了。其实整体的逻辑还是比较简单的:
        我们最开始把 1 传递进去,此时节点不为空,说明 1 节点实际存在,就把 1 存储到数组里面,之后我们把1的左右子节点分别再传入进去,反复进行  1 节点经历的操作,循环往复就完成了整个树的遍历

完整核心代码: 

class Solution {
public:
    void findallnodes(TreeNode* node ,vector<int>& d1)
    {
        if (node == NULL) return;
        d1.push_back(node->val);
        findallnodes(node->left,d1);
        findallnodes(node->right,d1);
    } 

    vector<int> preorderTraversal(TreeNode* root) {
            vector<int>result;
            findallnodes(root,result);
            return result;
    }
};

 其实中序遍历和后序遍历的逻辑都和前序遍历一样,就是数据在存储的时候要有所改动

中序遍历:

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);    // 中

手撕前中后序遍历(迭代):

 迭代法实际上是用栈来模拟递归的过程。

前序遍历:

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

详细解释:

这是一个二叉树的前序遍历算法的实现。算法的核心思想是使用栈来模拟递归遍历,具体步骤如下:

  1. 新建一个空栈st和一个空向量result;
  2. 若二叉树根节点为空,直接返回结果result;
  3. 将二叉树根节点压入栈中;
  4. 取出当前栈顶元素node,并将node的值加入result向量中;
  5. 若node的右子节点不为空,将右子节点压入栈中;
  6. 若node的左子节点不为空,将左子节点压入栈中;
  7. 重复步骤(4)-(6),直到栈为空;
  8. 返回向量result。

在实现过程中需要注意的是,因为前序遍历的顺序是根节点-左子树-右子树,所以需要先将右子节点入栈,再将左子节点入栈,才能保证取出栈顶元素时先访问左子树。另外,注意判断节点是否为空,为空时不需要入栈遍历。

中序遍历:

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. 新建一个空向量result和一个空栈st,同时初始化一个指针cur指向二叉树的根节点;
        2. 当当前指针cur不为空或栈st不为空时,执行下列操作:
           a. 若当前指针cur不为空,则将该节点加入栈st中,并将指针cur指向其左子节点,相当于递归遍历到左子树的最底层;
           b. 否则,即当前节点已经访问到最底层,从栈中将其弹出,并将其加入到结果向量result中,并将指针cur指向当前节点的右子节点,相当于返回到上一层节点继续遍历右子树;
        3. 重复步骤2,直到指针cur为空且栈st为空;
        4. 返回结果向量result。

在实现过程中,需要注意的是,由于中序遍历的顺序是左子树-根节点-右子树,所以需要先将整个左子树压入栈中,从栈中弹出的节点即为左子树最底层节点的父节点,并且该节点的左子树已经访问完毕,接下来需要访问该节点,并将指针cur指向右子节点,以此类推。另外,要注意判断节点是否为空,为空时不需要入栈和处理。

后序遍历:

class Solution {
public:
    vector<int> postorderTraversal(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;
    }
};

这是一个二叉树的后序遍历算法的实现。该算法使用栈来模拟递归遍历,具体步骤如下:

  1. 新建一个空栈st和一个空向量result;
  2. 若二叉树根节点为空,直接返回结果result;
  3. 将二叉树根节点压入栈中;
  4. 取出当前栈顶元素node,并将node的值加入result向量中;
  5. 若node的左子节点不为空,将左子节点压入栈中;
  6. 若node的右子节点不为空,将右子节点压入栈中;
  7. 重复步骤(4)-(6),直到栈为空;
  8. 返回向量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;
         
            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;
    }
};

这是一个二叉树的层序遍历算法的实现,即按照树的层次依次输出各节点的值。该算法使用队列来实现,具体步骤如下:

1. 新建一个空队列que,将根节点加入队列中;
2. 初始化一个空二维向量result,用于存储节点的值;
3. 当队列非空时,执行下列操作:
   a. 获取当前队列元素的个数size,表示当前层的节点个数;
   b. 新建一个空向量vec,用于存储当前层的节点值;
   c. 依次从队列中取出元素,并将其值加入到vec中,并将其左右子节点加入队列中;
   d. 将vec加入到result中;
4. 返回result向量,其中每个子向量表示一层的节点值。

在实现过程中,需要注意的是,在每一层遍历完成之后,需要将该层节点的值加入到二维向量result中。由于是按照层次遍历,因此需要保证同一层的节点先加入队列中,才能在后续的遍历中获取到该层节点的值。

递归法实现:

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

 这是一个二叉树的层序遍历算法的实现,与上一个算法不同的是,该算法采用递归实现。具体步骤如下:

1. 新建一个空二维向量result、一个初始深度depth为0的变量,并将根节点root作为当前节点cur;
2. 递归遍历当前节点cur的左子树和右子树,同时传递当前层的result二维向量和深度depth+1;
3. 将当前节点cur的值加入到result中对应深度的子向量中;
4. 当result中没有深度为depth的子向量时,新建一个空向量并加入到result中;
5. 返回result向量即可。

在实现过程中,需要注意的是,每个节点所在的深度取决于它的父节点深度,因此在递归遍历时深度depth需要加1。递归结束条件为当前节点cur为空。因为在递归遍历左子树和右子树之前,需要先将当前节点加入到result中对应深度的子向量中,因此result的初始值应为空。

总结:

        本篇详细的介绍了手撕二叉树遍历的各种常见方式,只有熟练的掌握树的遍历方式,我们才可以更加熟练的使用各种树结构,狠狠的拿下数据结构与算法。
 

如果我的内容对你有帮助,请点赞,评论,收藏。创作不易,大家的支持就是我坚持下去的动力!

【夜深人静学数据结构与算法 | 第四篇】手撕二叉树遍历

 文章来源地址https://www.toymoban.com/news/detail-490911.html

到了这里,关于【夜深人静学数据结构与算法 | 第四篇】手撕二叉树遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【夜深人静学数据结构与算法 | 第三篇】 二叉树

    目录  前言:  二叉树: 二叉树的种类:  二叉树的存储方式: 1. 链式存储 2. 数组存储 二叉树的遍历方式 深度优先遍历 广度优先遍历 总结: 本文将会详细的介绍各种常见的树以及相对应的概念,存储方式,遍历方式。树是经典的数据结构,因此我们虽然不能做到手撕各

    2024年02月11日
    浏览(47)
  • 【夜深人静学数据结构与算法 | 第十篇】动态规划

    目录 前言: 动态规划: 常见应用: 解题步骤:  动态规划的简化步骤: 案例: 509. 斐波那契数 - 力扣(LeetCode) 70. 爬楼梯 - 力扣(LeetCode) 62. 不同路径 - 力扣(LeetCode) 总结:         本文我们将为大家讲解一下动态规划的理论知识,并且会讲解几道力扣的经典例题。

    2024年02月11日
    浏览(50)
  • 【夜深人静学数据结构与算法 | 第九篇】栈与队列

    目录 ​前言: 栈: 栈的实际应用:  队列: 队列的实际应用: 总结:         栈与队列是我们学习的两个经典的数据结构,这两个数据结构应用广泛,在计算机内有很多底层应用,而很多算法也是依靠栈和队列来实现的,因此我们要想学好数据结构与算法,就要学好栈与

    2024年02月15日
    浏览(42)
  • 【夜深人静学习数据结构与算法 | 第十二篇】动态规划——背包问题

      目录  前言:  01背包问题: 二维数组思路: 一维数组思路: 总结:       在前面我们学习动态规划理论知识的时候,我就讲过要介绍一下背包问题,那么今天我们就来讲解一下背包问题。 在这里我们只介绍 01背包 ,至于分组背包和混合背包这种的已经属于竞赛级别的

    2024年02月12日
    浏览(49)
  • 【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式

    目录 前言:  中缀表达式:  后缀表达式: 中缀表达式转后缀表达式: 后缀表达式计算结果: 总结:  计算机在计算四则运算的时候,由于括号以及运算优先级的存在,并不能够很好的处理所有的运算,为了处理这种情况,我们引入了后缀表达式来优化算法。         

    2024年02月13日
    浏览(52)
  • 【夜深人静学数据结构与算法 | 第七篇】时间复杂度与空间复杂度

    前言:  引入:  时间复杂度:  案例: 空间复杂度: 案例: TIPS:        总结:         今天我们将来介绍时间复杂度和空间复杂度,我们代码的优劣就是依靠这个在评判,以此为背景,我们诞生出了不少的经典思路:用时间换空间,用空间换取时间。而大多数同学

    2024年02月10日
    浏览(62)
  • 夜深人静学32系列10——GPIO中断/NVIC/EXTI/SYSCFG详解,外部中断控制LED

    上期我们学习了GPIO驱动数码管/蜂鸣器/LED和按键等外设,本期我们一起来学习STM32中断的相关内容 当CPU正在处理某个事件的时候,外界发生了紧急事件请求,CPU需要暂停当前的工作,转而去处理这个紧急事件,处理完之后,再次回到之前被中断的地方,继续执行原来的工作,

    2024年01月16日
    浏览(46)
  • 【数据结构第四讲(排序算法)】我不信教不会你

    大家好啊✨ 先简单介绍一下自己💎 本人目前大二在读,专业是计算机科学与技术。 写博客的目的是督促自己记好每一章节的笔记,同时也希望结交更多同仁,大家互相监督,一起进步!☀️ 👀在这篇博客中,将会进行七种( 直接插入排序,希尔排序,选择排序,堆排序,

    2024年02月11日
    浏览(41)
  • 数据结构第四次实验-常用的内部排序算法

    一、实验目的 1.掌握常见的内部排序算法的思想及其适用条件; 2.掌握常见的内部排序算法的程序实现; 二、实验内容及要求 1、任务描述 设计一个内部排序算法模拟系统,利用该系统实现常用的 7 种排序算法,并测试 各种排序算法的性能。 实验内容:通过一个简单的菜

    2024年02月07日
    浏览(44)
  • Python篇——数据结构与算法(第四部分:希尔排序及其讨论、计数排序、桶排序、基数排序)

    希尔排序(shell sort)是一种分组插入排序算法 首先取一个整数d1=n/2,将元素分为d1个组,每组相邻两元素之间距离为d1,在各 组内 进行直接插入排序 取第二个整数d2=d1/2,重复上述分组排序过程,知道di=1,即所有元素在同一组内进行直接插入排序。 希尔排序每趟并不使某些

    2024年02月07日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包