「代码随想录」?叉树专题精讲 作者：程序员Carl 关于代码随想录 代码随想录官?：programmercarl 代码随想录开源项?Github：github/youngyangyang04/leetcode- master 代码随想录算法公开课 ，代码随想录的全部内容将由我（程序员 Carl）视频讲解 并开免费开放给?家。 《代码随想录》纸质版 已经出版。 代码随想录知识星球 上万录友在这?学习 代码随想录算法训练营 帮助录友?效刷完代码随想录。 PDF背景 该pdf是由公众号「代码随想录」?叉树专题的?章整理?来， 共7万字，40多张?叉树分 析图，33篇?叉树精品?章，详细讲解了40余道leetcode?叉树经典题?，由浅?深，? ?呵成，这是全?最全的?叉树专题讲解！ ?前已经发布了，?叉树 PDF、回溯算法PDF、贪?算法PDF、动态规划PDF，程序员求职 攻略PDF都?受获评，?家可以关注微信公众号：代码随想录，后台回复： 666，就可以获 取全部专题PDF了。 本PDF统?使?C++进?讲解，题解对应的其他语?版本，可以在代码随想录刷题? 站：programmercarl上查看，?持C++、Java，Python，Go，JavaScript等多 语?版本。 PDF难免会有笔误，或者?问题，所以内容会不断进?修正，其更新顺序为： Github >公众 号 >?站 > PDF。最新版本的PDF会?先在公众号?发布，不要错过咯。 如何使?这本PDF？ 就是按顺序刷就可以了！ 题?顺序都编排好了，按照 pdf?排好的题?顺序来刷效果最好，这份刷题顺序已经陪伴上 万录友（代码随想录的朋友们）。 本PDF覆盖的?叉树题??纲如下： （部分gif动画在pdf上看不了，还是需要在?站 programmercarl上观看） ?叉树理论基础篇 我们要开启新的征程了，?家跟上！ 说道?叉树，?家对于?叉树其实都很熟悉了，本?呢我也不想教科书式的把?叉树的基础 内容在啰嗦?遍，所以?下我讲的都是?些?较重点的内容。 相信只要耐?看完，都会有所收获。 ?叉树的种类 在我们解题过程中?叉树有两种主要的形式：满?叉树和完全?叉树。 满?叉树 满?叉树：如果?棵?叉树只有度为0的结点和度为2的结点，并且度为0的结点在同?层 上，则这棵?叉树为满?叉树。 如图所?： 这棵?叉树为满?叉树，也可以说深度为k，有2^k-1个节点的?叉树。 完全?叉树 什么是完全?叉树？ 完全?叉树的定义如下：在完全?叉树中，除了最底层节点可能没填满外，其余每层节点数 都达到最?值，并且最下??层的节点都集中在该层最左边的若?位置。若最底层为第 h 层，则该层包含 1~ 2^h -1 个节点。 ?家要??看完全?叉树的定义，很多同学对完全?叉树其实不是真正的懂了。 我来举?个典型的例?如题： 相信不少同学最后?个?叉树是不是完全?叉树都中招了。 之前我们刚刚讲过优先级队列其实是?个堆，堆就是?棵完全?叉树，同时保证??节点的 顺序关系。 ?叉搜索树 前?介绍的书，都没有数值的，??叉搜索树是有数值的了，?叉搜索树是?个有序树。 若它的左?树不空，则左?树上所有结点的值均?于它的根结点的值； 若它的右?树不空，则右?树上所有结点的值均?于它的根结点的值； 它的左、右?树也分别为?叉排序树 下?这两棵树都是搜索树 平衡?叉搜索树 平衡?叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是 ?棵空树或它的左右两个?树的?度差的绝对值不超过1，并且左右两个?树都是?棵平衡 ?叉树。 如图： 最后?棵不是平衡