每天一道算法练习题--Day15 && 第一章 --算法专题 --- -----------二叉树的遍历

这篇具有很好参考价值的文章主要介绍了每天一道算法练习题--Day15 && 第一章 --算法专题 --- -----------二叉树的遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

概述

二叉树作为一个基础的数据结构,遍历算法作为一个基础的算法,两者结合当然是经典的组合了。很多题目都会有 ta 的身影,有直接问二叉树的遍历的,有间接问的。比如要你找到树中满足条件的节点,就是间接考察树的遍历,因为你要找到树中满足条件的点,就需要进行遍历。

你如果掌握了二叉树的遍历,那么也许其他复杂的树对于你来说也并不遥远了

二叉数的遍历主要有前中后遍历和层次遍历。 前中后属于 DFS,层次遍历则可以使用 BFS 或者 DFS 来实现。只不过使用 BFS 来实现层次遍历会容易些,因为层次遍历就是 BFS 的副产物啊,你可以将层次遍历看成没有提前终止的 BFS。

DFS 和 BFS 都有着自己的应用,比如 leetcode 301 号问题和 609 号问题。

DFS 都可以使用栈来简化操作,并且其实树本身是一种递归的数据结构,因此递归和栈对于 DFS 来说是两个关键点。

DFS 图解:
每天一道算法练习题--Day15 && 第一章 --算法专题 --- -----------二叉树的遍历
BFS 的关键点在于如何记录每一层次是否遍历完成, 我们可以用一个标识位来表式当前层的结束。

对于前中后序遍历来说。首先不管是前中还是后序遍历,变的只是根节点的位置, 左右节点的顺序永远是先左后右。 比如前序遍历就是根在前面,即根左右。中序就是根在中间,即左根右。后序就是根在后面,即左右根。

下面我们依次讲解:

前序遍历

相关问题144.binary-tree-preorder-traversal
前序遍历的顺序是根-左-右

思路是:

  • 先将根结点入栈
  • 出栈一个元素,将右节点和左节点依次入栈
  • 重复 2 的步骤

总结: 典型的递归数据结构,典型的用栈来简化操作的算法。

其实从宏观上表现为:自顶向下依次访问左侧链,然后自底向上依次访问右侧链,如果从这个角度出发去写的话,算法就不一样了。从上向下我们可以直接递归访问即可,从下向上我们只需要借助栈也可以轻易做到。

整个过程大概是这样:
每天一道算法练习题--Day15 && 第一章 --算法专题 --- -----------二叉树的遍历

这种思路有一个好处就是可以统一三种遍历的思路. 这个很重要,如果不了解的朋友,希望能够记住这一点。

中序遍历

相关问题94.binary-tree-inorder-traversal
中序遍历的顺序是 左-根-右,根节点不是先输出,这就有一点点复杂了。

  • 根节点入栈
  • 判断有没有左节点,如果有,则入栈,直到叶子节点

此时栈中保存的就是所有的左节点和根节点。

  1. 出栈,判断有没有右节点,有则入栈,继续执行 2

值得注意的是,中序遍历一个二叉查找树(BST)的结果是一个有序数组,利用这个性质有些题目可以得到简化, 比如230.kth-smallest-element-in-a-bst, 以及98.validate-binary-search-tree

后序遍历

相关问题145.binary-tree-postorder-traversal
后序遍历的顺序是 左-右-根
这个就有点难度了,要不也不会是 leetcode 困难的 难度啊。

其实这个也是属于根节点先不输出,并且根节点是最后输出。 这里可以采用一种讨巧的做法, 就是记录当前节点状态,如果:

  • 当前节点是叶子节点或者
  • 当前节点的左右子树都已经遍历过了,那么就可以出栈了。

对于 1. 当前节点是叶子节点或者当前节点的左右子树都已经遍历过了,那么就可以出栈了。
对于 2. 当前节点的左右子树都已经遍历过了, 只需要用一个变量记录即可。最坏的情况,我们记录每一个节点的访问状况就好了,空间复杂度 O(n) 但是仔细想一下,我们使用了栈的结构,从叶子节点开始输出,我们记录一个当前出栈的元素就好了,空间复杂度 O(1), 具体请查看上方链接。

层次遍历

层次遍历的关键点在于如何记录每一层次是否遍历完成, 我们可以用一个标识位来表式当前层的结束。
每天一道算法练习题--Day15 && 第一章 --算法专题 --- -----------二叉树的遍历
具体做法:

  • 根节点入队列, 并入队列一个特殊的标识位,此处是 null
  • 出队列
  • 判断是不是 null, 如果是,则代表本层已经结束。我们再次判断是否当前队列为空,如果不为空继续入队一个 null,否则说明遍历已经完成,我们什么都不不用做
  • 如果不为 null,说明这一层还没完,则将其左右子树依次入队列。

相关问题:
每天一道算法练习题--Day15 && 第一章 --算法专题 --- -----------二叉树的遍历

双色标记法

我们知道垃圾回收算法中,有一种算法叫三色标记法。 即:

  • 用白色表示尚未访问
  • 灰色表示尚未完全访问子节点
  • 黑色表示子节点全部访问

那么我们可以模仿其思想,使用双色标记法来统一三种遍历。

其核心思想如下:

  • 使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色。
  • 如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈。
  • 如果遇到的节点为灰色,则将节点的值输出。

使用这种方法实现的中序遍历如下:

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node is None: continue
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res

可以看出,实现上 WHITE 就表示的是递归中的第一次进入过程,Gray 则表示递归中的从叶子节点返回的过程。 因此这种迭代的写法更接近递归写法的本质。

如要实现前序、后序遍历,只需要调整左右子节点的入栈顺序即可。可以看出使用三色标记法, 其写法类似递归的形式,因此便于记忆和书写,缺点是使用了额外的内存空间。不过这个额外的空间是线性的,影响倒是不大。

虽然递归也是额外的线性时间,但是递归的栈开销还是比一个 0,1 变量开销大的。换句话说就是空间复杂度的常数项是不同的,这在一些情况下的差异还是蛮明显的。

划重点:双色迭代法是一种可以用迭代模拟递归的写法,其写法和递归非常相似,要比普通迭代简单地多。

Morris 遍历

我们可以使用一种叫做 Morris 遍历的方法,既不使用递归也不借助于栈。从而在 O ( 1 ) O(1) O(1) 空间完成这个过程。

如果你需要使用 O ( 1 ) O(1) O(1) 空间遍历一棵二叉树,那么就要使用 Morris 遍历。

这个算法考察相对少,作为了解即可。

def MorrisTraversal(root):
    curr = root

    while curr:
        # If left child is null, print the
        # current node data. And, update
        # the current pointer to right child.
        if curr.left is None:
            print(curr.data, end= " ")
            curr = curr.right

        else:
            # Find the inorder predecessor
            prev = curr.left

            while prev.right is not None and prev.right is not curr:
                prev = prev.right

            # If the right child of inorder
            # predecessor already points to
            # the current node, update the
            # current with it's right child
            if prev.right is curr:
                prev.right = None
                curr = curr.right

            # else If right child doesn't point
            # to the current node, then print this
            # node's data and update the right child
            # pointer with the current node and update
            # the current with it's left child
            else:
                print (curr.data, end=" ")
                prev.right = curr
                curr = curr.left

划重点:Morris 是一种可以在 O ( 1 ) O(1) O(1) 空间遍历二叉树的算法。

总结

本文详细讲解了二叉树的层次遍历和深度优先遍历。

对于深度优先遍历,我们又细分为前中后序三种遍历方式。

最后我们讲解了双色遍历和 Morris 遍历。这两种方式可以作为了解,不掌握也没关系。

另外,如果题目要求你实现迭代器(就是调用一次输出一个二叉树的值),那么前面讲的迭代的方式就非常适用了。比如这道题 Binary Search Tree Iterator文章来源地址https://www.toymoban.com/news/detail-428944.html

到了这里,关于每天一道算法练习题--Day15 && 第一章 --算法专题 --- -----------二叉树的遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 计算机组成原理基础练习题第一章

    有些计算机将一部分软件永恒地存于只读存储器中,称之为() A.硬件    B.软件 C. 固件     D.辅助存储器 输入、输出装置以及外界的辅助存储器称为() A.操作系统    B.存储器 C.主机       D. 外围设备 完整的计算机系统包括() A.运算器、存储器、控制器   

    2024年02月04日
    浏览(57)
  • 数据库系统概述——第一章 绪论(知识点复习+练习题)

    ✨ 博主: 命运之光 🦄 专栏: 离散数学考前复习(知识点+题) 🍓 专栏: 概率论期末速成(一套卷) 🐳 专栏: 数字电路考前复习 🦚 专栏: 数据库系统概述 ✨ 博主的其他文章: 点击进入博主的主页​​​​​ 前言: 身为大学生考前复习一定十分痛苦,你有没有过以

    2024年02月09日
    浏览(53)
  • 《Lua程序设计第四版》 第一部分自做练习题答案

    Lua程序设计第四版第一部分语言基础自做练习题答案,带⭐为重点。 运行阶乘的示例并观察,如果输入负数,程序会出现什么问题?试着修改代码来解决问题 输入负数,程序会死循环,修改如下 分别使用-l参数和dofile运行twice示例,并感受你喜欢哪种方式 载入库,在 lua解释

    2024年02月13日
    浏览(49)
  • 《Lua程序设计第四版》 第一部分前8章自做练习题答案

    Lua程序设计第四版第一部分语言基础自做练习题答案,带⭐为重点。 运行阶乘的示例并观察,如果输入负数,程序会出现什么问题?试着修改代码来解决问题 输入负数,程序会死循环,修改如下 分别使用-l参数和dofile运行twice示例,并感受你喜欢哪种方式 载入库,在 lua解释

    2024年02月13日
    浏览(157)
  • 练习题----顺序栈算法

    ​输入一个包括 \\\'(\\\' 和 \\\')\\\' 的字符串string ,判断字符串是否有效。要求设计算法实现检查字符串是否有效,有效的字符串需满足以下条件: A. 左括号必须用相同类型的右括号闭合。 B. 左括号必须以正确的顺序闭合。 C. 每个右括号都有一个对应的相同类型的左括号。 ​该题需

    2024年04月26日
    浏览(42)
  • <算法学习>动态规划练习题

    本篇文章为初学动态规划时的练习题。参考优质博客学习后根据伪代码描述完成代码。记录一下用于以后复习。 给定一个有n行数字组成的数字三角形. 试设计一个算法, 计算出从三角形的顶至底的一条路径, 使该路径经过的数字和最大. 算法设计: 对于给定的n行数字组成的三角

    2024年01月17日
    浏览(47)
  • Matlab:遗传算法,模拟退火算法练习题

    1、遗传算法 (1) 遗传算法 是一种基于自然选择原理和自然遗传机 制的搜索(寻优)算法,它是模拟自然界中的生命进化机制,在人工系统中实现特定目 标的优化。遗传算法的实质是通过群体搜索技术,根据适者生存的原则逐代进化,最终 得到最优解或准最优解。它必须

    2024年01月21日
    浏览(46)
  • 拓扑排序 (算法思想+图解+模板+练习题)

    有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列。 无向图没有拓扑序列。 首先我们先来解释一下什么是有向无环图: 有向就是我们两个结点之间的边是有方向的,无环的意思就是整个序列中没有几个结点通过边形成一个圆环。 下图就是一个有向无环图,它也一定

    2024年02月03日
    浏览(64)
  • 【算法设计与分析】动态规划-练习题

    输入一个整数数组 S[n] ,计算其最长递增子序列的长度,及其最长递增子序列。 定义 k ( 1 ≤ k ≤ n ) k (1 ≤ k ≤ n) k ( 1 ≤ k ≤ n ) ,L[k]表示以 S[k] 结尾的递增子序列的最大长度。子问题即为 L[k]。 对于每一个k,我们都遍历前面0~k-1的所有的数,找出最大的L[i],且 S [ k ] L [

    2024年02月03日
    浏览(57)
  • 数据结构与算法系列之习题练习

    💗 💗 博客:小怡同学 💗 💗 个人简介:编程小萌新 💗 💗 如果博客对大家有用的话,请点赞关注再收藏 🌞 括号匹配问题。 用队列实现栈。 用栈实现队列。 设计循环队列。 有效的括号 //用栈来实现 //左括号进栈 右括号出栈并销毁如果不匹配则return //设置两个队列,入栈

    2024年02月11日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包