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）是一种用于遍历树或图的算法。
  • 沿着树的
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_43569680/article/details/115471262

智能推荐

Leetcode 栈刷题心得单调栈用法-程序员宅基地

文章浏览阅读134次。leetcode刷题过程中取得了部分心得：在栈的专题下，主要的考察点是栈先进后出的特性，当遍历一个字符串或者一个列表的时候，可能会出现类似于字符串解码，或者是接雨水之类的问题，这时就需要从后往前出栈，只有栈才能满足这样的特性。因此当出现从后往前输出已经遍历的过的值的时候，就应该考虑使用栈这种数据结构。首先我们最应该掌握的栈的一种用法就是单调栈leetcode中的每日温度接雨水等都是典型的单调栈解题、以接雨水题为例class Solution { public int t_栈刷题

国标流媒体-H265摄像头如何实现网页直播_网页播放h265的流媒体-程序员宅基地

文章浏览阅读2.9w次。介绍目前安防监控行业，基本所有的摄像头都支持H264编码，但是已经有部分摄像头开始支持H265，并且支持H265的摄像机已经越来越多。H265相比H264有着很多优势，是压缩更高，网络传输消耗的带宽更小，相同码率下H265视频更清晰。H264目前已经可以在各种web浏览器、客户端等进行解码播放，但是H265目前还没用得到大部分浏览器的支持，没法直接在web端播放。达到目的为了最终能再各种终端..._网页播放h265的流媒体

CentOS下yum安装FFmpeg_yum偷懒-程序员宅基地

文章浏览阅读606次。一、yum安装FFmpeg1. 最偷懒的方式就是yum安装了，自动解决依赖。不过CentOS系统默认无FFmpeg源，企业版 Linux 附加软件包EPEL源也不包含，需要手动添加yum源配置/etc/yum.repos.d/dag.repo: [dag]name=Dag RPM Repository for Red Hat Enter_yum偷懒

Linux命令之"ping"_如何ping64字节数据的-|是什么-程序员宅基地

文章浏览阅读1.4k次。Linux系统的ping命令是常用的网络命令，它通常用来测试与目标主机的连通性，我们经常会说“ping一下某机器，看是不是开着”、不能打开网页时会说“你先ping网关地址192.168.1.1试试”。它通过发送ICMP ECHO_REQUEST数据包到网络主机（send ICMP ECHO_REQUEST to network hosts），并显示响应情况，这样我们就可以根据它输出的信息来确定目标_如何ping64字节数据的-|是什么

windows API:ShowWindow_windows api showwindow-程序员宅基地

文章浏览阅读745次。ShowWindow(hwnd,SW_SHOWNORMAL);//显示窗口UpdateWindow(hwnd);//刷新窗口 该句可有可无BOOL ShowWindow( HWND hWnd, //handle to window int nCmdShow //show state);SW_HIDE 、 WS_MAXMIZE_windows api showwindow

ROS2编译运行节点代码_ros2 node 编译和启动-程序员宅基地

文章浏览阅读877次，点赞17次，收藏14次。自用自用。_ros2 node 编译和启动

随便推点

OpenStack-Ocata版+CentOS7.6 云平台环境搭建 — 4.镜像服务（glance）-程序员宅基地

文章浏览阅读223次。节点配置信息说明：控制节点：controller：IP：192.168.164.128hostname&hosts：likeadmin计算加点：Nova：IP：192.168.164.129hostname&hosts：likenode块存储节点:cinder：IP：192.168.164.136hostname&hosts：likebloc..._"option \"verbose\" from group \"default\" is deprecated for removal."

android-调用手机程序打开本地html文件（7.0以上、7.0以下区别）_intent.action_view 打开本地html-程序员宅基地

文章浏览阅读4k次。1、方法，7.0以下直接运行，不用管2、3步 public static void openFile_html(String string) { File file = new File(string); if (!file.exists()) { Log.e(cn.uiautomator.Constants.TAG, "文件不存在：" + string); return; } Int_intent.action_view 打开本地html

Cadence每日一学_08 | OrCAD绘制原理图 - 元器件封装FootPrint信息处理及显示_cadence怎么查看原理图的封装-程序员宅基地

文章浏览阅读6.5k次，点赞7次，收藏63次。在绘制原理图的时候，元器件只显示标号和值，一般不显示封装信息，如图，这篇文章讲述如何处理元器件的封装信息并显示出来。在原理图中元器件的封装信息绘制有三种方法：单个元器件编辑并显示；整个原理图工程批量设置显示元器件的封装（不能设置显示）；创建元器件的原理图库时直接设置封装并显示；1.单个元器件编辑并显示填写该元器件封装：设置封装显示出来：2.整个原理图工程批量设置..._cadence怎么查看原理图的封装

51单片机的存储结构_51单片机哈佛结构-程序员宅基地

文章浏览阅读2.5k次，点赞3次，收藏11次。51单片机的存储结构为哈佛结构，即程序存储器（ROM）与数据存储器（ROM）空间是各种独立的。_51单片机哈佛结构

2021年NOC大赛编程马拉松赛道图形化小低组模拟卷,包含答案_2021年noc编程马拉松 真题-程序员宅基地

文章浏览阅读922次。2020-2021 NOC核桃编程马拉松图形化小低组模拟卷。_2021年noc编程马拉松 真题

云原生|kubernetes|centos7下离线化部署kubesphere-3.3.2---基于kubernetes-1.22.16（从网络插件开始记录）_离线部署kubesphere-程序员宅基地

文章浏览阅读1.7k次。kubesphere的离线化部署指的是通过自己搭建的harbor私有仓库拉取镜像，完全不依赖于外部网络的方式部署。我的kubernetes集群是一个单master节点，双工作节点，总计三个节点的版本为1.22.16的集群。该集群只是初始化完成了，网络插件什么的都还没有安装，本文计划做一个整合，将metricserver，网络插件，storageclass nfs存储插件的部署整合到这一个文章中来，在将kubesphere这些部署依赖安装完毕后，在将镜像推送到我自己搭建的一个带有证书的harbor_离线部署kubesphere

推荐文章

热门文章

相关标签