null - 程序员宅基地

LeetCode数据结构之树_leedcode上的树如何表示-程序员宅基地

LeetCode数据结构之树

1.树的基本概念

树是一种非线性数据结构。
树结构的基本单位是节点。
节点之间的链接，称为分支（branch）。
节点与分支形成树状，结构的开端，称为根（root），或根结点。
根节点之外的节点，称为子节点（child）。
没有链接到其他子节点的节点，称为叶节点（leaf）。

如下图是一个典型的树结构：
在这里插入图片描述
其他重要概念：

树的高度：节点到叶子节点的最大值就是其高度。
树的深度：高度和深度是相反的，高度是从下往上数，深度是从上往下。因此根节点的深度和叶子节点的高度是 0。
树的层：根开始定义，根为第一层，根的孩子为第二层。
二叉树，三叉树，。。。 N 叉树，由其子节点最多可以有几个决定，最多有 N 个就是 N 叉树。

2.二叉树

2.1 二叉树概念

二叉树是树结构的一种，两个叉就是说每个节点最多只有两个子节点，我们习惯称之为左节点和右节点。（注意这个只是名字而已，并不是实际位置上的左右）

2.2 二叉树分类

完全二叉树
满二叉树
二叉搜索树
平衡二叉树
红黑树
… …

2.3 二叉树存储

链表存储
数组存储。非常适合完全二叉树

3.二叉树问题解决

一个口诀：
一个中心，两个基本点，三种题型，四个重要概念，七个技巧

3.1 一个中心

树的遍历就是这个中心！！！

树的遍历的本质就是去把树里边儿的每个元素都访问一遍。
树虽然只能从根开始访问，但是我们可以选择在访问完毕回来的时候做处理，还是在访问回来之前做处理，这两种不同的方式就是后序遍历和先序遍历。
树的遍历又可以分为两个基本类型，分别是深度优先遍历和广度优先遍历。这两种遍历方式并不是树特有的，但却伴随树的所有题目。

树的遍历迭代写法——双色标记法
模仿垃圾回收算法之一：三色标记法
即：用白色表示尚未访问；灰色表示尚未完全访问子节点；黑色表示子节点全部访问
双色标记法的核心思想：

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

中序遍历的实现：
实际上 WHITE 就表示的是递归中的第一次进入过程，Gray 则表示递归中的从叶子节点返回的过程。因此这种迭代的写法更接近递归写法的本质。

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

实现前序、后序遍历，也只需要调整左右子节点的入栈顺序即可，其他部分是无需做任何变化。

3.2 两个基本点

深度优先遍历（以下简称 DFS，还可以细分为前中后序遍历）和广度优先遍历（以下简称 BFS，还可以细分为带层的和不带层的），这就是两个基本点。

DFS 适合做一些暴力枚举的题目，DFS 如果借助函数调用栈，则可以轻松地使用递归来实现。
在这里插入图片描述

3.2.1 深度优先遍历（DFS）

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历树或图的算法。
沿着树的

本文链接：https://blog.csdn.net/qq_43569680/article/details/115471262

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

clickhouse单机读写性能测试（附带运行截图）_clickhouse单机性能-程序员宅基地

文章浏览阅读4.6k次，点赞3次，收藏4次。使用版本20.10.3.30云主机配置数据及操作来源https://clickhouse.tech/docs/zh/getting-started/example-datasets/star-schema/表类型及数据量表名表结构表定义语句表数据量 customer CREATE TABLE customer\ (\ C_CUSTKEY UInt32,\ C.._clickhouse单机性能

springboot整合之统一异常处理_springboot统一异常处理-程序员宅基地

文章浏览阅读5.4k次，点赞8次，收藏46次。springboot整合实战 springboot整合之统一异常处理_springboot统一异常处理

iOS-class方法和objc_getClass方法-程序员宅基地

文章浏览阅读1.7k次，点赞2次，收藏2次。根据上一篇博客iOS-class、object_getClass、objc_getClass、objc_getMetaClass区别的研究发现，qi's_objc_getclass

【数据结构】查找1——线性表的查找（顺序查找、折半查找、分块查找）_图顺序查找-程序员宅基地

文章浏览阅读2.8k次。【数据结构】查找1——线性表的查找（顺序查找、折半查找、分块查找）_图顺序查找

zip包解压时报malformed input off : 0, length : 1-程序员宅基地

文章浏览阅读843次。使用ZipArchiveInputStream而非ZipInputStream的原因主要有以下两点：支持更多的压缩格式：ZipArchiveInputStream是Apache Commons Compress库中提供的类，能够支持多种压缩格式，包括Zip、Gzip、Tar、Jar等。而ZipInputStream是Java标准库中的类，只能读取普通的Zip文件。因此，如果需要处理多种压缩格式的文件，使用ZipArchiveInputStream会更加方便。更多的选项和功能：ZipArchiveInp_malformed input off : 0, length : 1

switch case结合枚举值使用，借助枚举的值来做case分支判断_switch case 枚举-程序员宅基地

文章浏览阅读8.3k次，点赞9次，收藏22次。https://blog.csdn.net/m0_37754981/article/details/80022169参考资料_switch case 枚举

随便推点

RedisTemplate使用lua脚本_redistemplate lua-程序员宅基地

文章浏览阅读2.2k次。LUA简介Lua 是一个小巧的脚本语言。是巴西里约热内卢天主教大学（Pontifical Catholic University of Rio de Janeiro）里的一个研究小组，由Roberto Ierusalimschy、Waldemar Celes 和 Luiz Henrique de Figueiredo所组成并于1993年开发。其设计目的是为了嵌入应用程序中，从而为应用程序提供灵活的扩展和定制功能。Lua由标准C编写而成，几乎在所有操作系统和平台上都可以编译，运行。Lua并没有提供强大的_redistemplate lua