|
|
## <center>二叉树</center>
|
|
|
|
|
|
递归序 每个节点都到达三次
|
|
|
|
|
|
#### 二叉树的先序、中序、后序遍历
|
|
|
|
|
|
先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树
|
|
|
中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树
|
|
|
后序：任何子树的处理顺序都是，先左子树、再右子树、然后头节点
|
|
|
|
|
|
#### 递归方式实现二叉树的先序、中序、后序遍历
|
|
|
|
|
|
1）理解递归序
|
|
|
2）先序、中序、后序都可以在递归序的基础上加工出来
|
|
|
3）第一次到达一个节点就打印就是先序、第二次打印即中序、第三次即后序
|
|
|
|
|
|
#### X 祖先节点 交集
|
|
|
|
|
|
<br />
|
|
|
<br />
|
|
|
  X是一棵二叉树的某一个节点，A是二叉树先序遍历X的左边部分，B是二叉树后序遍历X右边部分，AB相交的结果是且仅是X的所有父节点。
|
|
|
1、X的所有父节点在先序遍历的左边，X的所有父节点在后序遍历的右边，交集一定包含所有父节点
|
|
|
2、X的所有子节点在先序遍历的左边，X的所有子节点在后序遍历的左边，交集一定不包含所有子节点
|
|
|
3、A不包含所有祖先节点的右兄弟节点，B不包含所有祖先节点的左兄弟节点
|
|
|
  X的所有祖先节点、X自己、X的子节点、X或者X的父节点作为左树的右兄节点、X或者X的父节点作为右树的左兄节点
|
|
|
<br />
|
|
|
<br />
|
|
|
|
|
|
#### 非递归方式实现二叉树的先序、中序、后序遍历
|
|
|
|
|
|
1）任何递归函数都可以改成非递归
|
|
|
2）自己设计压栈的来实现
|
|
|
|
|
|
#### 实现二叉树的按层遍历
|
|
|
|
|
|
1）其实就是宽度优先遍历，用队列
|
|
|
2）可以通过设置flag变量的方式，来发现某一层的结束
|
|
|
|
|
|
#### 实现二叉树的序列化和反序列化
|
|
|
|
|
|
1）先序方式序列化和反序列化
|
|
|
2）按层方式序列化和反序列化
|
|
|
|
|
|
#### 将多叉树编码为二叉树 LeetCode431
|
|
|
|
|
|
#### 打印二叉树
|
|
|
|
|
|
#### 二叉树的宽度
|
|
|
|
|
|
求二叉树最宽的层有多少个节点
|
|
|
|
|
|
#### 找出某个节点的后继节点
|
|
|
|
|
|
  二叉树结构如下定义：
|
|
|
|
|
|
```Java
|
|
|
Class Node {
|
|
|
V value;
|
|
|
Node left;
|
|
|
Node right;
|
|
|
Node parent;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
  给你二叉树中的某个节点，返回该节点的后继节点。
|
|
|
|
|
|
#### 折纸
|
|
|
|
|
|
  请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。 如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
|
|
|
给定一个输入参数N，代表纸条都从下边向上方连续对折N次。 请从上到下打印所有折痕的方向。
|
|
|
例如:N=1时，打印: down N=2时，打印: down down up
|
|
|
|
|
|
主要解题思路是递归
|
|
|
|
|
|
二叉树的递归套路
|
|
|
1）假设以X节点为头，假设可以向X左树和X右树要任何信息
|
|
|
2）在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要）
|
|
|
3）列出所有可能性后，确定到底需要向左树和右树要什么样的信息
|
|
|
4）把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S
|
|
|
5）递归函数都返回S，每一棵子树都这么要求
|
|
|
6）写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息
|
|
|
|
|
|
#### 判断两颗二叉树是否相同 LeetCode100
|
|
|
|
|
|
#### 判断一个二叉树是否对称 LeetCode101
|
|
|
|
|
|
#### 获取一个二叉树的高度 LeetCode104
|
|
|
|
|
|
#### 用先序数组和中序数组重建一个二叉树 LeetCode105
|
|
|
|
|
|
先序遍历的第一个元素是头结点，先序遍历剩余部分左边是左节点的先序，右边是右节点的先序，中序遍历左边是左节点的中序，右边是右节点的中序。递归构建二叉树，递归函数入参为先序遍历的起止index，中序遍历的起止index，返回头结点。
|
|
|
|
|
|
#### 二叉树按层遍历收集节点 LeetCode107 LeetCode102
|
|
|
|
|
|
使用LinkedList(有序，快速插入)，递归将每一层的节点入队、出队。
|
|
|
|
|
|
#### 平衡二叉树 LeetCode110
|
|
|
|
|
|
给定一棵二叉树的头节点head，返回这颗二叉树是不是平衡二叉树
|
|
|
判断二叉树是否是平衡二叉树
|
|
|
左子树的高度和右子树的高度相差不超过1，则称为平衡二叉树。
|
|
|
|
|
|
#### 搜索二叉树 LeetCode98
|
|
|
|
|
|
判断二叉树是否是搜索二叉树
|
|
|
递归解决
|
|
|
|
|
|
#### 路径总和 LeetCode112
|
|
|
|
|
|
#### 达标路径总和 LeetCode113
|
|
|
|
|
|
#### 二叉树的最大距离
|
|
|
|
|
|
给定一颗二叉树的头结点，任何两个节点之间都存在距离，返回整颗二叉树的最大距离。
|
|
|
|
|
|
#### 判断完全二叉树
|
|
|
|
|
|
判断二叉树是否是完全二叉树
|
|
|
按照二叉树的定义判断，逐行遍历
|
|
|
递归套路
|
|
|
|
|
|
#### 满二叉树
|
|
|
|
|
|
给定一棵二叉树的头节点head，返回这颗二叉树是不是满二叉树
|
|
|
|
|
|
#### 最大的二叉搜索子树
|
|
|
|
|
|
给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的头节点。
|
|
|
|
|
|
#### 最大的二叉搜索子树大小
|
|
|
|
|
|
给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的大小。
|
|
|
|
|
|
#### 最低公共祖先
|
|
|
|
|
|
给定一棵二叉树的头节点head，和另外两个节点a和b。返回a和b的最低公共祖先。
|
|
|
a、b可能在head的左右子树，也可能在同一棵子树。
|
|
|
使用中间变量
|
|
|
1、遍历整棵树，用map保存所有节点的父节点
|
|
|
2、遍历a的所有父节点，用set保存
|
|
|
3、遍历b的所有父节点，看set中是否存在
|
|
|
后序遍历递归套路
|
|
|
|
|
|
#### 派对的最大快乐值
|
|
|
|
|
|
  员工信息的定义如下:
|
|
|
|
|
|
```Java
|
|
|
class Employee {
|
|
|
public int happy; // 这名员工可以带来的快乐值
|
|
|
List<Employee> subordinates; // 这名员工有哪些直接下级
|
|
|
}
|
|
|
```
|
|
|
|
|
|
  公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。 叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。
|
|
|
  这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则：
|
|
|
  1.如果某个员工来了，那么这个员工的所有直接下级都不能来
|
|
|
  2.派对的整体快乐值是所有到场员工快乐值的累加
|
|
|
  3.你的目标是让派对的整体快乐值尽量大
|
|
|
  给定一棵多叉树的头节点boss，请返回派对的最大快乐值。
|
