二叉树介绍

一.树的概念

树的图：

1.结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6

2.树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6

3.叶子结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I...等节点为叶结点

4.双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点

5.孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点

6.根结点：一棵树中，没有双亲结点的结点；如上图：A

7.结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

8.树的高度或深度：树中结点的最大层次； 如上图：树的高度为4。

二.二叉树

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空

2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

3. 二叉树不存在度大于2的结点

4. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

二叉树的几种情况：

满二叉树：: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完比特就业课全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。（完全二叉树可以简单的说为从上到下从左到右依次放就是完全二叉树）

二叉树的性质：

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 (i>0)个结点

2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0)

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1（推导的公式）：

4. 具有n个结点的完全二叉树的深度k为 上取整

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点

若2i+1<n，左孩子序号：2i+1，否则无左孩子

若2i+2<n，右孩子序号：2i+2，否则无右孩子

6.在完全二叉树中，如果节点总个数为奇数，则没有度为1的节点，如果节点总个数为偶数，只有一个度为1的节点。

三.练习题

1.选B（度为0的节点个数比度为2的节点个数多一个。）

2.选A（第三张图是当节点个数为奇数的时候计算的，和偶数一样的计算方式，只不过没有单独的一个度为0的节点。）

3.选B（这道题就是上图奇数个节点的情况）

4.选B（用性质算）

四.二叉树的存储和遍历

1.顺序存储（在堆的时候将）

2.类似于链表的链式存储

3.二叉树的遍历

（1）前序遍历（根 左 右）

这里先从A这个根开始遍历，之后再到A的左树马，之后就是将B看为一个根,也要遵循根左右的规则，那么此时遍历B的左树D，D又成为了根，此时遍历D的左树，D的左树为空，那么回到D这个根，遍历D的右树，D的右树为空，此时D这个根遍历完返回到B这个根，遍历B的右树，B的右树也为空，此时返回到B树，再返回到根A，此时再遍历A的右树C，同理C此时当作根，遍历C的左树E，E此时为根，遍历E的左树，左树为空，返回到根E，遍历E的右树，E的右树为空，返回根E，E遍历完返回到根C，遍历C的右树，C的右树为F，F此时也当作根，来遍历F的左树，F的左树为空，返回到根F，遍历F的右树，F的右树为空，返回根F，F遍历完F，返回到根C，C遍历完，返回到根A，A的右树也遍历完了则前序遍历完成。顺序为ABDCEF

（2）中序遍历（左 根 右）

中序遍历的法则是 左 根 右 ，从根A开始先进入二叉树，此时是中序遍历，要左边走完才打印根A，所以此时没有打印根A，进入A的左树B，B也是根继续走B的左树D，D也是根继续走D的左树，D的左树为空，则返回到D，此时左走完了走到了根，则打印D，再走D的右树，右树为空，此时返回根D，D遍历完返回B，B的左树走完，此时打印B，走入B的右树，B的右树为空，B遍历完返回到根A，打印A，因为此时A的左树遍历完了，进入A的右树C，此时C也为根，先走C的左树E，E为根，先走E的左树，E的左树为空，返回到E，打印E，再走E的右树，E遍历完返回到根C，打印C，进入C的右树F，F的左树为空，返回到F打印F，再走到F的右树，右树为空，遍历完F返回到C，C遍历完，返回到A，遍历完二叉树。顺序DBAECF

（3）.后序遍历（左 右 根）

后序遍历，规则 左 右 根，此时先进入二叉树，根A开始，进入A的左树B，B为根进入B的左树D，此时D的左树为空回到D，此时没有任何节点被打印，当继续遍历D的右树为空返回到D的时候打印D，此时返回到B，B的右树为空，遍历完B此时打印B，返回到A，遍历A的右树，C为根进入C的左树E，E的左树为空进入右树也为空，遍历完E，此时打印E，回到C，进入C的右树F，F的情况和E相同不赘述，打印了F回到了C，C遍历完左右树，打印C，回到A，A此时遍历完左右树，打印A。顺序：DBEFCA

（4）层序遍历（从上到下，从左到右，依次遍历）
4.代码

（1）树节点的结构：

（2）.这里先用很low的方式创建一个树：

（3）树的前序遍历：（自己画图的大致流程，后面的流程都是一样的）

（4）树的中序遍历：

（5）树的后序遍历：

（6）非递归的层序遍历：（非递归的层序遍历需要有一个临时变量cur记录当前节点，并且把此时这个节点的不为空的左右子树传入队列中进行入队操作，然后再通过临时变量来进行出队，就可以实行层序遍历）画图解释：

（7）非递归的前序遍历：（通过栈来进行压栈数据，先遍历每个节点的左子树，当最后一个节点的左子树为空的时候再通过top通过栈内元素pop接收这个在栈顶的元素，让cur来遍历这个节点的右子树，依次循环往复。）

（8）中序遍历的非递归实现：（中序遍历和前序遍历的代码都是一样的，就是打印的位置不同，中序遍历是左根右，那么在遍历右子树之前打印这个节点就可以啦）

（9）后序遍历的非递归实现：(刚开始的思路和上面两种遍历的方式是一样的，但是在pop栈里面的元素的时候就不一样了，这里需要把这个节点的右子树走完才能进行打印，所以就需要对这个节点的右子树进行判断。再进行判断的时候不是直接把这个节点直接pop出来而是需要用peek去看一下这个节点的右节点是否为null不为null就需要继续遍历这个右节点。这里需要注意的是，当遍历到E的时候，这里E的左子树是null的，所以cur就是null，这里的top直接peek 栈中的节点，也就是E节点，如果E节点的右子树为null的话，那么直接就打印E节点并且pop但是E节点的右子树有一个H，那么cur就会拿到这个节点，然后再进行判断，H的左右子树都为null那么就直接打印H并且弹出H，此时栈中的栈顶元素是E，那么此时top拿到E再进行判断E的右子树是否为null，不为空，那么cur又拿到了H这个节点，所以这里就循环了，这里也就是和上面两个循环不同的地方，这里就需要哪一个prev来记录下来这个右子树的节点，当回到E这个结点的时候，通过prev上次拿到的是H的节点如果等于top就是E节点的右子树的话，那么E的右子树走完回来了，直接打印E并且pop出E的这个节点，这里就是不同的地方。)

五.二叉树练习题

1.选A，这就是她的层序遍历，并且她是完全二叉树。

2.选A 这道题画图的话就是下一张图中的树。先序遍历的第一个为根，中序遍历中间E就为根，就可以进行画图了。

3.选D

4.选A

5.无法根据前序和后序来画出树的图，因为前后序确定的是树的根。

六.二叉树的节点个数计算

1.一个树的节点个数等于根节点加上这个根的左树和右树的节点个数：总结就是这个根的左树+右树+1就是这个树的节点个数，也就是说，每个节点都可以看成一个根，然后求每个根的节点个数再通过递归传回数值的大小就可以计算出树的节点个数。

2.通过前序遍历来计算节点个数：（把打印数据变成size++就行了，原理都是一样的）

3.求叶子节点个数：1.子问题思路：整棵树的叶子节点等于左子树的叶子节点+右子树的叶子节点个树 2.遍历思路：以某种方式遍历树，为叶子就++（叶子是没有左子树和右子树的节点为叶子）

第一种方法实现：

第二种方法实现：

3.第K层节点的个数:（计算的方法就是通过递归的思想算第k-1层左树的节点和右树的节点，当为第一层的时候直接返回1，然后递推结束，开始回归）

4.算树的高度：（树的高度是通过递归来实现的，需要注意的是这里不能直接return递归的语句也就是图三框住的return语句，如果直接这样使用会导致递归的重复调用，使用的时间就会更长会超出时间限制，因为当你递归出HeightTree(root.left) 为5的时候并且HeightTree(root.right)为4的时候，HeightTree(root.left)>HeightTree(root.right)，你要HeightTree(root.left)+1此时你还需要你计算一次HeightTree(root.left)的大小，重复计算花费的时间更多。）（时间复杂度为O（N））

5.找指定数据：（找到数据的时候一定要将数据保留下来而不是继续循环看图二错误写法就是没有在递归的时候把正确的数据return回来而只return回来null，图三分别为正确的流程（黑红线）和错误流程（只有红线））（时间复杂度是O（N），因为需要遍历每个节点）

七.二叉树OJ题

1.两个树是否相同：（思路：判断两个数是否相同需要从两个方面来判断，首先就是判断两个数的结构是否相同，第一种情况就是这两个树的一个根节点一个为空，一个不为空，那么肯定是不相同的，第二种情况就是两个根节点都是空的话那么这个根节点就是相同的，然后还需要继续判断后面的节点是否相同。第三种情况就是根节点都存在的情况下，根的值不同，那么也是直接返回false。递归思路就在画图）（时间复杂度为O（p和q之间节点个数的最小值））

2.这个树是否为另一棵树的子树：（思路：如果这两棵树相同，那么两棵树构成子树关系，然后通过递归root的左子树和子树进行对比，再通过root的右子树和子树进行对比，如果上述三个条件都不满足就是不为子树关系，或者root为空的时候也就是root这棵树遍历完了都不满足则这两棵树不为子树关系，递归详细画图）（时间复杂度：root的节点为m subroot的节点个数为n 那么空间复杂度为O(m*n) 因为每次在root节点上都要遍历一次subroot的节点）

3.翻转二叉树：（思路就是通过前序遍历交换每个节点的左右子树）（比较简单不画图）

4.判断一个二叉树是否为平衡二叉树（平衡二叉树表示该树的所有节点的左右子树深度差小于等于1）

方法一：时间复杂度为O（N^2）（时间为O（N^2）是因为在计算每个节点的深度的时候就遍历了全部节点，当判断树是否平衡的时候也要遍历这个树的每个节点，那么就重复了，所以才是O（N^2），这个方法是通过计算每个节点的左右子树的节点个数然后做差算出差值的绝对值小于等于1就为平衡二叉树。（HeighTree是上面计算指定根的深度。）画图解释。需要注意的是图三这幅图是不为平衡二叉树的，当9作为根节点的时候，左子树的深度是2，右子树为0，左右子树的差值大于1了就不是平衡二叉树。

方法二：时间复杂度为O（N）不重复计算。（思路就是当左子树深度减去右子树的深度的绝对值大于1那么就直接返回-1，如果满足平衡二叉树的条件的话也就是说左右子树的深度差值小于等于1，那么就直接返回左子树和右子树之间最大的深度+1）

5.对称二叉树：（思路：对称二叉树需要的是左子树和右子树对称，那么也和树是否相同的思路一样，先从结构考虑，如果一个为空，一个不为空，肯定不对称，两个都为空，就对称，最后再从值的方面考虑如果两个都不为空，但是值不一样就是不对称的。最后还需要判断每一个树的左树的左节点是否等于右树的右节点，画图解释）

6.二叉树的创建和遍历：（这道题是在牛客上面写的，需要注意的点有几个，首先就是我们需要注意的是一开始牛客上的界面是图三这种，我们这里是输入的字符串需要用到字符串的输入，并且我们会使用到空格就需要使用nextLine而不是next来输入字符串，因为next输入的字符串不能有空格。之后就是这道题需要通过前序遍历创建一个二叉树，并且通过中序遍历输出，那么中序遍历和树节点的创建就不说了，这道题的思路还是比较简单，这里还需要注意的是就是当我们在判断字符串中的第i个字符不是字符的时候，里面进行的语句就是创建一个节点并且设置左右节点，这里需要注意的是我们创建了一个结点之后就需要进行i++，因为当此时如果在左子树递归或者右子树递归语句的后面才施行i++那么就会导致思路错误了。整体来说思路就是判断第i个字符是不是空格，不是空格进行创建一个节点，并且让i++再进行左子树和右子树的递归，如果是空格就直接i++。）图四是画图解释：

这里i是静态变量带来的危害：如果在main方法中创建两个TreeNode对象每次i就无法从0开始，因为第一次遍历完之后i就在第一个字符串的末尾了。

7.非递归的层序遍历（顺序表来写）：（总体思路和非递归层序遍历差不多，唯一的差别就是需要用二维数组来实现这个二叉树，需要注意的是，每层的创建应该在计算size大小的时候进行重新开辟，而不是直接在外面创建一个数组然后一直add。图二就是错误示范）

全是同一个数据的原因是：当我们实现完这个层序遍历之后list的地址都是一样的，那么list1 进行add三次都是同一个list，那么就是这三个元素的add都是同一个地址，那么就是相同的数据。

8.找到两个节点的最近公共祖先：（下面四种就是公共祖先的情况）

方法一：通过直接递归来写：（第一种情况如果p和q之间有一个为root，那么直接返回root就可以了，第二种情况p和q分别在根的左右子树，那么就需要通过递归来进行找到p和q的，然后再通过语句来判断是哪种情况，如果都在p和q就是刚刚说的在左右子树那么就返回根节点root，如果都是在左子树或者右子树就返回最先找到的那个节点就可以了。）（图解第二张）

方法二：用栈来写：（这种情况用堆好解释，简单的说类比链表的分支）（思路：将p和q的路径记录下来，再通过像链表的相交的想法来进行两个栈的对比，如果第一个元素相同那么后面的元素都是相同的，直接返回第一个出栈的节点。如果第一个栈顶元素不同，就一起出栈栈顶元素，不断比较，比较到结束完都没有那么就直接返回null说明没有公共祖宗节点。其中getPath的方法不好写，因为我们需要递归的从根的左右子树来找到这个节点，还需要注意的是，当这个节点的左右子树都找不到p或者q的时候我们就需要把这个节点从栈里面弹出，这是需要注意的地方。还有就是需要注意每次左子树遍历和右子树遍历都需要写一个判断条件不能一直往下走。）

9.前序遍历和中序遍历创建树：（大致的思路就是先通过前序遍历和中序遍历来确定根节点，确定根节点之后就可以通过中序遍历中的根节点来确定左右子树，根的左边就是左子树，右边的数据就是右子树，然后再通过定义一个inBegin和inEnd来进行每个节点的遍历。因为inBegin和inEnd是每个节点需找自己左右子树的范围，所以这样就可以确定每个节点的左右子树。这里从E开始进行遍历，在中序遍历中我们可以知道，E的左边数据为左子树，右边数据为右子树，那么此时我们需要先找左子树的数据，因为先序遍历是根左右，所以此时开始找E的左子树，那么此时E左子树的inBegin和inEnd的范围就是0到在中序遍遍历E的下标的左边一个下标，此时就是inEnd的范围，所以此时我们就需要写一个语句来找到每个节点的位置，这样才能在找左子树的时候确定他的inEnd的大小。此时找左子树的过程是一个递归的过程，当inBegin大于inEnd的时候就是没有节点了，此时就就代表递归结束了。还需要注意的是，在最开始我们需要定义一个成员变量才能让先序遍历中的下标不被函数栈帧销毁，因为我们再找节点的时候是通过先序遍历的顺序来找的每个节点。右子树也是如此。这里还需要注意的是，我们传入根节点的inEnd的时候必须是中序遍历数组长度-1.不能直接传入中序遍历数组的大小，因为在找数据的时候我们是通过inBegin和inEnd来循环找数据的，如果你直接传入中序遍历数组的大小的话，那么我们循环语句就是直接写的是 i < inEnd 当inBegin和inEnd相等的时候就找不到这个数据了，但是这个数据就是inBegin和inEnd相等的时候的位置，所以就会导致我们找不到这个节点的位置也就导致无法找到这个节点子树的inEnd的大小了，因为inEnd是等于这个节点下标减一。右子树则是将inBegin 等于 这个节点下表+1，inEnd不变）

10.后序遍历和中序遍历：（这里和前序遍历的差不太多，唯一的差别就是先递归根的右子树再左子树，并且此时遍历这个后续遍历的数组的时候是通过最后一个位置的元素来进行 -- 来进行的，因为根节点在最后一个位置，通过 -- 来找到数据，而且后序遍历是通过左 右 根来进行的，那么反起来找数据那么就是根 右 左，所以和前序遍历是反的，其他的思路都是一样滴）

11.二叉树创建字符串：（这里是通过StringBuilder来进行字符串的添加通过实例1，我们可以知道根节点是没有括号的，那么直接就可以append（root.val）然后再进行左子树的判断，第一种情况就是左子树不为空，通过实例1，我们知道先他是先进行增加一个左括号，然后通过左子树的递归来进行增加节点，递归完之后在增加右括号，如果左子树为空，那么还需要判断右子树是否为空，如果右子树也为空此时直接返回，如果右子树不为空的话我们看示例二，示例二中2的左子树为空，右子树不为空，那么这里直接增加了一个括号的，那么此时也是直接增加一个括号，此时左子树的情况说完，来说右子树的情况，如果右子树不为空的话，也是和左子树一样先一个左括号然后再递归，递归完之后在增加上右括号。如果右子树为空的话就直接return就好了）