顿搜
飞过闲红千叶，夕岸在哪
类目归类
二叉树——算法设计 · 篇八
08/17
一、二叉树的遍历
GitHub地址：二叉树的遍历.cpp
两种方法
1、递归的方法
2、非递归的方法
二、二叉树的基本应用
GitHub地址：二叉树的基本应用.cpp
- ①、层次遍历二叉树
使用队列或者双端队列
- ②、二叉树中节点的个数
递归求解
- ③、二叉树的深度
左子树深度与右子树深度的最大值
- ④、二叉树的宽度
二叉树的宽度就是节点最多的那层中节点的个数
- ⑤、二叉树中根到叶子节点的路径
递归调用左子树与右子树，并依次打印节点值
- ⑥、判断两棵二叉树是否结构相同
递归调用左右子树，都相同即相同
- ⑦、二叉树的镜像转换
左右子树交换，然后递归调用
三、有序数组转化为 BST
GitHub地址：有序数组转化为 BST.cpp
- ①、将一个有序数组高效地插入到二叉搜索树中
1、初始化一个节点
2、找到有序数组的中间点作为根节点
3、递归调用创造左子树和右子树
四、二叉搜索树的基本操作
GitHub地址：二叉搜索树的基本操作.cpp
- ①、构造二叉查找树
根据当前值与当前结点的值的大小，选择插入到左子树还是右子树
- ②、删除二叉搜索树种的某个节点
1、首先需要查找该元素是否存在
2、删除的节点被找到，接下来进行删除的操作，分为三种情况
3、第一种情况是待删除节点没有孩子，那么直接删除
4、如果此结点有一个孩子，直接用待删除结点的孩子代替删除结点
5、如果此结点有两个孩子，找一个合适的值替代
五、遍历序列构造 BST
GitHub地址：遍历序列构造 BST.cpp
- ①、由一个二叉搜索树的前序序列和中序序列构造树
1、前序序列第一个元素即为根结点，在中序序列中找到该点
2、那么中序序列中左右部分分别为左子树和右子树
3、同样的进行递归即可
- ②、由中序和后序序列遍历构造二叉树
1、后序序列最后一个元素即为根结点，在中序序列中找到该点
2、那么中序序列中左右部分分别为左子树和右子树
3、同样的进行递归即可
六、链表和二叉树的转化
GitHub地址：链表和二叉树的转化.cpp
- ①、将有序单链表转化为二叉搜索树
1、快慢指针找到有序单链表的中间节点
2、递归的将前后两个子有序单链表转化为二叉搜索树
- ②、将二叉树转化为双向链表
和中序遍历思路一样
1、递归处理左子树，当左子树处理完后，左子树就是一个双向链表，并且记录该链表的最后一个指针
2、把左子树链表中的最后一个节点与当前节点双向连接（中序遍历算法此处是打印当前节点）
3、递归处理右子树，当右子树处理完后，右子树就是一个双向链表，同时整个双向链表建立完成。
七、查找根到叶子的固定路径值
GitHub地址：查找根到叶子的固定路径值.cpp
- ①、根到叶子路径之和为指定值
1、递归遍历，并记录结点和，如果和达到指定值，并且已到叶子结点即可
- ②、从根到叶子所有路径中，路径和最大的值
递归遍历，找最大值即可
八、判断序列是否为 BST 的后序遍历
GitHub地址：判断序列是否为 BST 的后序遍历.cpp
方法
1、对于后序遍历，一定要明白最后一个元素是根节点，
2、左子树都比根元素大，右子树都比根元素小
3、然后递归检测左右子树
九、求节点的最大距离
GitHub地址：求节点的最大距离.cpp
- ①、二叉树中任意两个节点的最远距离，这里的距离就是边的个数
1、最远距离的两个节点都在右子树
2、最远距离的两个节点都在左子树
3、最远的两个节点一个在右子树，一个在左子树，那么就是左子树中最远节点到当前节点的距离加上右子树中最远节点到当前节点的距离
十、二叉树中求两结点的最低公共父结点
GitHub地址：求两节点的最低公共父节点.cpp
1、从根结点开始查找，如果当前结点是其中一个结点，则该结点即为最低公共父结点
2、递归遍历左子树，如果两个结点都不在左子树中，则最低公共父结点要么是当前结点，要么在右子树中
3、递归遍历右子树，如果两个结点都不在右子树中，则最低公共父结点要么是当前结点，要么在左子树中
4、如果一个结点在左子树，一个结点在右子树，则当前结点为最低公共父结点。
十一、字典树（Trie）的基本操作
GitHub地址：字典树（Trie）的基本操作.cpp
略
