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

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

智能推荐

FX3/CX3 JLINK 调试_ezusbsuite_qsg.pdf-程序员宅基地

文章浏览阅读2.1k次。FX3 JLINK调试是一个有些麻烦的事情，经常有些莫名其妙的问题。设置参见 c:\Program Files (x86)\Cypress\EZ-USB FX3 SDK\1.3\doc\firmware 下的 EzUsbSuite_UG.pdf 文档。常见问题： 1.装了多个版本的jlink，使用了未注册或不适当的版本选择一个正确的版本。JLinkARM_V408l，JLinkA_ezusbsuite_qsg.pdf

用openGL+QT简单实现二进制stl文件读取显示并通过鼠标旋转缩放_qopengl如何鼠标控制旋转-程序员宅基地

文章浏览阅读2.6k次。** 本文仅通过用openGL+QT简单实现二进制stl文件读取显示并通过鼠标旋转缩放，是比较入门的级别，由于个人能力有限，新手级别，所以未能施加光影灯光等操作，未能让显示的stl文件更加真实。****效果图：**1. main.cpp```cpp#include "widget.h"#include <QApplication>int main(int argc, char *argv[]){ QApplication a(argc, argv); _qopengl如何鼠标控制旋转

刘焕勇&王昊奋｜ChatGPT对知识图谱的影响讨论实录-程序员宅基地

文章浏览阅读943次，点赞22次，收藏19次。以大规模预训练语言模型为基础的chatgpt成功出圈，在近几日已经给人工智能板块带来了多次涨停，这足够说明这一风口的到来。而作为曾经的风口“知识图谱”而言，如何找到其与chatgpt之间的区别，找好自身的定位显得尤为重要。形式化知识和参数化知识在表现形式上一直都是大家考虑的问题，两种技术都应该有自己的定位与价值所在。知识图谱构建往往是抽取式的，而且往往包含一系列知识冲突检测、消解过程，整个过程都能溯源。以这样的知识作为输入，能在相当程度上解决当前ChatGPT的事实谬误问题，并具有可解释性。

如何实现tomcat的热部署_tomcat热部署-程序员宅基地

文章浏览阅读1.3k次。最重要的一点，一定是degbug的方式启动，不然热部署不会生效，注意，注意！_tomcat热部署

用HTML5做一个个人网站，此文仅展示个人主页界面。内附源代码下载地址_个人主页源码-程序员宅基地

文章浏览阅读10w+次，点赞56次，收藏482次。html5 ，用css去修饰自己的个人主页代码如下：<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xh..._个人主页源码

程序员公开上班摸鱼神器！有了它，老板都不好意思打扰你！-程序员宅基地

文章浏览阅读201次。开发者（KaiFaX）面向全栈工程师的开发者专注于前端、Java/Python/Go/PHP的技术社区来源：开源最前线链接：https://github.com/svenstaro/gen..._程序员怎么上班摸鱼

随便推点

UG\NX二次开发改变Block UI界面的尺寸_ug二次开发调整对话框大小-程序员宅基地

文章浏览阅读1.3k次。改变Block UI界面的尺寸_ug二次开发调整对话框大小

基于深度学习的股票预测（完整版，有代码）_基于深度学习的股票操纵识别研究python代码-程序员宅基地

文章浏览阅读1.3w次，点赞18次，收藏291次。基于深度学习的股票预测数据获取数据转换LSTM模型搭建训练模型预测结果数据获取采用tushare的数据接口（不知道tushare的筒子们自行百度一下，简而言之其免费提供各类金融数据 , 助力智能投资与创新型投资。）python可以直接使用pip安装tushare!pip install tushareCollecting tushare Downloading https://files.pythonhosted.org/packages/17/76/dc6784a1c07ec040e74_基于深度学习的股票操纵识别研究python代码