前言本次梳理的内容是数据结构题目中的“树”。如果你看到树这样的数据结构，你会头疼不已，很难理解。如果是这样的话，那么这篇文章可能会对你有所帮助。俗话说，要想掌握和理解，就必须先了解它的概念、性质等内容。围绕以下几点展开树的介绍👇树的基本概念，基本术语，树的类型，二叉树的概念，二叉树的遍历，二叉树的题目总结，脑图👇树数据采集的基本概念。或者你可以把它想象成一个“抽象数据结构”或者是实现了这种抽象数据类型的数据结构，用来模拟一个具有树状结构属性的数据集合。那么根据维基百科给出的定义，我们似乎可以这样理解：它是由n(n>0)个有限节点组成的具有层次关系的集合。它被称为“树”，因为它看起来像一棵倒置的树，这意味着它的根朝上，叶子朝下。它具有以下特点：每个节点只有有限数量的子节点或没有子节点；没有父节点的节点称为根节点；每个非根节点只有一个父节点；除根节点外，每个子节点都可以分成多个不相交的子树；当树中没有循环（cycle）的时候，我们需要拿出一张图片来看看👇从图中，以上五个特征可以很好的得出A节点是根节点，没有父节点，所以是根节点。除根节点（A）外，其他节点都有父节点，每个节点只有有限的子节点或没有子节点。从某个结点开始，可以分成很多子树，比如从B结点开始，就是这样。既然我们对树有了一定的了解，那么我们就需要了解它的一些术语。Basicterms树的基本术语为了更规范的概括，这里给出的描述来自维基百科：“节点的度”：一个节点包含的子树的个数，称为该节点的度；“树的度”：在一棵树中，最大的节点度称为树的度；“叶节点”或“终端节点”：度数为零的节点；“非终端节点”或“分支节点”：非零度的节点；""父节点"或"父节点"：如果一个节点包含子节点，则称该节点为它的子节点的父节点；"子节点"或"子节点"：一个节点包含的子树的根节点称为节点的子节点；“兄弟节点”：具有相同父节点的节点称为兄弟节点；节点的“层次”：从根的定义开始，根为第一层，子节点为根是第二层，以此类推；“深度”：对于任意节点n，n的深度是从根到n的唯一路径的长度，根的深度为0；“高度”：对于任意节点n，n的高度为从n到一片叶子的最长路径长，所有叶子的高度为0；“表亲节点”：父节点在同一层的节点是表亲；“祖先的nodes”：从根节点到该节点的分支上的所有节点；”“Descendants”：以某个节点为根的子树中的任何节点都称为该节点的后代；“森林”：m(m>=0)棵不相交树的集合称为森林。你可以结合上面的图来理解这些概念。通过两者的结合，你一定会对这棵树有更深入的了解。有了上面的基本概念和一些专业术语的掌握，接下来我们就需要对树木进行分类，看看有哪些种类的树木。树的种类了解了树的概念和基本术语后，接下来我们需要展开的是树的种类。我们可以以维基百科为依据作为分类标准👇无序树：树中任意节点的子节点之间没有顺序关系。这种树称为无序树，也称为自由树；有序树：树中任意节点的子节点之间存在顺序关系。这种树称为有序树；完全二叉树：对于一棵二叉树，假设它的深度为d（d>1）。除第d层外，其他层的节点数都达到最大值，第d层的所有节点从左到右连续紧密排列。这样的二叉树称为完全二叉树；平衡二叉树（AVL树）：当且仅当任意节点的两个子树的高度差不大于1颗二叉树；排序二叉树（英文：BinarySearchTree））：又称二叉搜索树、有序二叉树；fullbinarytree：所有的叶子节点都是最底层的一棵完全二叉树；二叉树：每个节点最多有两个子树的树称为二叉树；哈夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；B-tree：一对读写操作优化的自平衡二叉搜索树，保持数据有序，有两个以上的子树。既然树木的分类那么多，难道我们都需要一一掌握吗？个人觉得掌握二叉树的结构就够了，二叉树也是最简单也是应用最广泛的一类树。那么接下来，我们来介绍一下二叉树。二叉树的概念二叉树是一种典型的树状树结构。顾名思义，二叉树是每个节点最多有两棵子树的树结构，通常子树被称为“左子树”和“右子树”。二叉树从这张图的内容来看，应该很清楚的展示了二叉树的结构。至于二叉树的性质，大家可以参考下图作为补充知识。我个人认为这不是重点。如果说二叉树的性质很重要，那么我们需要掌握的应该是它的遍历方法。二叉树遍历我们知道二叉树遍历有三种常见的遍历方法，分别是以下三种：前序遍历中序遍历后序遍历对于任何一种遍历方法，我们不仅需要掌握它的递归版本，在同时，对于它的递归版本来说，就是考察一个人算法的基本功，那么接下来，我们就来看看吧。前序遍历点此练习二叉树的前序遍历给你二叉树的根节点root，返回其节点值的“前序”遍历。假设我们模拟假数据👇input:[1,null,2,3]1\2/3output:[1,3,2]然后根据我们对前序遍历的理解，可以写出解题伪代码👇//TianTianUp//*functionTreeNode(val,left,right){//*this.val=(val===undefined?0:val)//*this.left=(left===undefined?null:left)//*this.right=(right===undefined?null:right)//*}letinorderTraversal=(root,arr=[])=>{if(root){inorderTraversal(root.left,arr)arr.push(root.value)inorderTraversal(root.right,arr)}returnarr}非递归版👇对于非递归，我们需要一个数据结构来存储它的节点，需要用到栈，其思路可以借鉴👇根节点为目标节点，开始遍历其子节点1.访问目标节点2.左孩子入栈->直到左孩子为空节点3.节点退出Stack，伴随右孩子作为目标节点，然后依次执行1、2、30){while(current){res.push(current.val)stack.push(current)current=current.left}current=stack.pop()current=current.right}returnres}中序遍历给定一棵二叉树，返回它的中序遍历。例子：输入：[1,null,2,3]12/3输出：[1,3,2]进阶：递归算法很简单，你能完成迭代算法吗？递归版本👇constinorderTraversal=(root,arr=[])=>{if(root){inorderTraversal(root.left,arr)arr.push(root.val)inorderTraversal(root.right,arr)}returnarr}非递归版本，这里不做解释，和前序遍历一样，思路也是一样的，用栈来维护节点信息。constinorderTraversal=(root,arr=[])=>{conststack=[],res=[]letcurrent=rootwhile(current||stack.length>0){while(current){stack.push(current)current=current.left}current=stack.pop()res.push(current.val)current=current.right}returnres}后续遍历给定一棵二叉树，返回其后序遍历。例子：输入：[1,null,2,3]12/3输出：[3,2,1]进阶：递归算法很简单，你能完成迭代算法吗？来源：LeetCode链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal版权所有归领扣网所有。商业转载请联系官方授权，非商业转载请注明出处。递归版本👇constpostorderTraversal=(root,arr=[])=>{if(root){postorderTraversal(root.left,arr)postorderTraversal(root.right,arr)arr.push(root.val)}returnarr}非递归版本#128071;其实嗯，做完前两个，你会发现有套路~constpostorderTraversal=(root,arr=[])=>{conststack=[],res=[]letcurrent=root,last=null//last指针记录前一个节点while(current||stack.length>0){while(current){stack.push(current)current=current.left}current=stack[stack.length-1]if(!current.right||current.right==last){current=stack.pop()res.push(current.val)last=currentcurrent=null//继续出栈}else{current=current.right}}returnres}二叉树的层次遍历??链接：二叉树的顺序遍历给你一颗二叉树，请返回“层级遍历”得到的节点值。（即逐层，从左到右访问所有节点）。例子：二叉树：[3,9,20,null,null,15,7],3/920/157返回其层次遍历结果：[[3],[9,20],[15,7]]来源：LeetCode链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal版权归LeetCode所有。商业转载请联系官方授权，非商业转载请注明出处。递归版本👇constlevelOrder=function(root){if(!root)return[]letres=[]dfs(root,0,res)returnres}functiondfs(root,step,res){if(root){if(!res[step])res[step]=[]res[step].push(root.val)dfs(root.left,step+1,res)dfs(root.right,step+1,res)}}非递归版本👇这里使用了队列的数据结构，使用了先进先出的机制。constlevelOrder=(root)=>{letqueue=[],res=[]if(root)queue.push(root);while(queue.length){letnext_queue=[],now_res=[]while(queue.length){root=queue.shift()now_res.push(root.val)root.left&&next_queue.push(root.left)root.right&&next_queue.push(root.right)}queue=next_queueres.push(now_res)}returnres}主题摘要还是那句话，题没完没了，剩下的就靠刷leetcode了。我也准备了一些二叉树的常用题集，题的质量还是不错的👇二叉树的最小深度?二叉树的最大深度?同树?BST和对称BST的范围?将排序数组转换为BST?二叉树的层次遍历Ⅱ??BST的最近公共祖先??验证BST??PathSumIII??有重复元素III??计算右侧小于当前元素的元素个数???
