牛客网《BAT面试算法精品课》视频链接：《BAT面试算法精品课》 笔记链接： 牛客网《BAT面试算法精品课》笔记一：排序 牛客网《BAT面试算法精品课》笔记二：字符串 牛客网《BAT面试算法精品课》笔记三：队列和栈 牛客网《BAT面试算法精品课》笔记四：链表 牛客网《BAT面试算法精品课》笔记五：二分搜索 牛客网《BAT面试算法精品课》笔记六：二叉树 牛客网《BAT面试算法精品课》笔记七：位运算 牛客网《BAT面试算法精品课》笔记八：排列组合 牛客网《BAT面试算法精品课》笔记九：概率 牛客网《BAT面试算法精品课》笔记十：大数据 牛客网《BAT面试算法精品课》笔记十一：动态规划 二叉树节点的结构：
二叉树类型的题目为常考题型： 1.能够结合队列，栈，链表，字符串等很多数据结构 2.需要掌握图的基本遍历方式，比如BFS和DFS 3.需要掌握递归函数的使用，并自己设计出递归过程 4.与实际工作结合紧密 二叉树先序，中序，后序：
常见题型： 案例1. 用递归方式和非递归方式分别实现二叉树的先序，中序和后序的遍历打印 递归先序遍历：
非递归先序遍历：
递归中序遍历：
非递归中序遍历：
递归后序遍历： 
非递归后序遍历： 方法一： 
方法二：
不管是递归方法还是非递归方法，遍历整棵树的时间复杂度都是O(N)，N为二叉树的节点数，额外空间复杂度为O(L)，L为二叉树的层数。 二叉树按层遍历：
案例2. 
定义两个变量： Last：表示正在打印的当前行的最右节点 nlast：表示下一行的最右节点 每一层都做从左到右的宽度优先搜索遍历，当last节点跑到最右边，让last=nlast，nlast继续下一行越来越右。
二叉树的序列化和反序列化：
案例3. 二叉树被记录成文件的过程叫做二叉树的序列化，通过文件内容重建原来二叉树的过程叫做二叉树的反序列化。给定一颗二叉树的头结点head，并已知二叉树节点值的类型为32位整型。请设计一种二叉树序列化和反序列化的方案，并用代码实现。 先序遍历对二叉树进行序列化：
为什么要在一个节点值的后面非要加上一个叹号或者其它的特殊字符来表示一个字符的结束呢？因为如果不标记，最后产生的结果可能会有歧义，比如：
一棵二叉树先序遍历得到的结果，如何进行反序列化： 
01.可以看到我们用什么样的方式序列化，就用什么样的方式反序列化。 02.一棵树序列化的结果是唯一的，唯一的结果生成的二叉树也是唯一的 按层遍历的方式对二叉树进行序列化： 01.用队列来进行二叉树的按层遍历，即宽度优先遍历 02.除了访问节点的顺序是按层遍历之外，对结果字符串的处理。与之前介绍的处理方式一样 03.反序列化过程同理 二叉树的子树： 
平衡二叉树(AVL)： 第3棵树的2号节点的高度差超过了1，所以第三棵树不是平衡二叉树
案例4. 给定一颗二叉树的头结点head，判断这棵树是否是平衡二叉树。 
首先，如果左子树不是平衡二叉树，返回false；如果左子树是的，继续往下执行，如果右子树不是平衡二叉树，返回false。如果左子树和右子树都是平衡二叉树，那么就看LH和RH的差值的绝对值是否大于1. 搜索二叉树（BST）： 搜索二叉树又叫二叉查找树，二叉排序树
案例5. 给定一棵二叉树的头结点head，请判断这颗树是否是搜索二叉树 
满二叉树和完全二叉树： 满二叉树：
完全二叉树：
案例6. 给定一棵二叉树的头节点head，判断一棵树是否是完全二叉树
在面试中，二叉树结点类型仅包括：数据项，左孩子，右孩子 在工程中，往往多一条指向父节点的指针 一般默认面试中的二叉树节点结构不包含指向父节点的指针，除非特别说明。 后继节点与前驱结点：
案例7.
普通方法：
最优解法： 如果node节点和node后继节点之间的实际距离为L，最优解法只用走过L个节点，时间复杂度位O(L)，额外空间复杂度O(1)
案例8. 
所有折痕的结构是一颗满二叉树：
案例9. 一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请找到这两个错误节点。
案例10. 
解题思路：
步骤：
案例11.
思路：
步骤：
牛客网《BAT面试算法精品课》笔记六：二叉树
Last updated: