二叉树节点结构
递归序
什么是递归序
- 递归序是二叉树递归遍历的一种套路
- 按照递归序，每个节点会经过3次，第一次是初次进入节点，第二次是左树返回节点，第三次是右树返回节点
例如，存在下面的树：
那么按照头节点、左树、有树的遍历顺序，一定有这样的递归序：
1 2 3 3 3 2 4 4 4 2 1 5 6 6 6 5 7 7 7 5 1，根据递归序，我们可以轻松得到前序遍历、中序遍历、后续遍历的序列：
- 前序遍历，第一次经过节点的序列：1 2 3 4 5 6 7
- 中序遍历，第二次经过节点的序列：3 2 4 1 6 5 7
- 后序遍历，第三次经过节点的序列：3 4 2 6 7 5 1
递归序是一种思想，它便于我们更加容易的写出二叉树递归的code，像下面这样：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public static class Node{
private int value;
private Node left;
private Node right;
}
public void f(Node head){
if (head == null){
return;
}
// 这里是第一次进入head节点
f(head.left);
// 这里是从左树返回后，第二次进入head节点
f(head.right);
// 这里是从右树返回后，第三次进入head节点
}
}
如果是前序遍历，就在第一次进入节点的时候打印value，中序遍历、后序遍历同理
非递归遍历二叉树
任何递归都可被改成非递归，二叉树递归也不例外，只要我们不使用系统压栈，而是自己手动压栈就行了
先序遍历
准备好一个栈：
- 先入头节点
- 弹出并输出节点value，如果节点有左右孩子节点，先压入右节点，再压入左节点
- 重复1、2操作，直到栈为空
中序遍历
准备一个栈：
- 先压入头节点，再依次压入左边界（每棵树的左节点）
- 弹出节点并打印value，如果有右节点，压入右节点，再依次压入右节点所在子树的左边界
- 重复1、2操作，直到栈为空
后序遍历
准备两个栈，s1压入栈，s2收集栈：
- 先压入头节点
- 弹出节点，不打印保存到收集栈，如果有左右孩子，先左孩子后右孩子压入栈
- 重复1、2操作，直到压入栈为空，然后弹出收集栈，直至收集栈为空，弹出的序列就是后续遍历
总结
非递归中，难度最大应该就是中序遍历了，因为说是非递归其实做法里面都体现的递归思想，下面对三种非递归方式进行总结：
- 先序遍历比较简单，就不重复总结了
- 中序遍历：从序列来将：左树 –> 父节点 –> 右树，为了按照这个顺序打印出来，我们需要对左树不断递归，将左树一个个存入栈直到左树为空，这时从栈中弹出节点cur，此时cur就是最左树，因此优先存储它的val，然后对cur的右树重复需要最左树的操作，如果右树为空，从栈中继续弹出，重复操作直至栈为空，并且cur为null，此时当前节点的左树val都已存储，并且右树为空，所以停止打印
- 后序遍历需要准备两个栈，st1弹出的顺序为： 父节点 –> 右节点 –> 左节点，以弹出的顺序存入另外一个栈st2，那么st2的出栈顺序就是：左节点 –> 右节点 –> 父节点，那么经推测最先存入st1的顺序是：父节点 –> 左节点 –> 右节点，注意是先弹出父节点，再压入左节点和右节点
真题链接：
如何直观的打印一棵树
这类题目通常是设计题
宽度优先遍历（层序遍历）
准备一个队列（在Java中，LinkedList虽然底层结构是双向链表但也可以作为队列使用）：
- 先压入头节点
- 队列弹出节点并打印，如果存在左右孩子节点，先左后右压入队列
- 重复1、2操作，直到队列为空
注意：因为队列是先进先出的特点，所以不用一次性把该层的节点全部弹出，但再某些情况下，比如BFS求树的深度，最好通过队列容量一次性弹出所有的节点
真题链接：
二叉树的递归套路
该套路可以解决大部分的树形DP问题，并且思路和递归特别像，其实呢就是动态规划：父类问题由子类（条件）推出，套路如下：
- base条件：即当节点为空时应该返回什么？
- 左右子树的递归应该返回什么结果（左右子树的结果应该是形式相同的）给当前节点，当前节点根据左右子树的返回条件判断以当前节点为根节点的树的状态，下面列出的各个问题大多可以使用这个思路，少数题目则不适合
判断二叉树是否是二叉搜索树
什么是二叉搜索树？左树总小于根节点，右树总大于根节点，同时树内没有相同的元素，因为二叉搜索树在构建的时候相同的数据不会重复插入 思路：
- 中序遍历二叉树，如果数值一直升序，说明是BST，否则不是，注意：需要一个全局变量用于存储前序节点，这个方法可以使用递归的方式，也可以使用迭代+栈的方式
- 利用递归套路：
- 如果左树或右树不是BST，那么整棵树就不是BST
- 如果左树和右树都是BST，但（左树的最大值大于当前节点的值）或者（当前节点的值大于右树的最小值）
如何将以上信息整理返回给父亲节点呢？
1
2
3
4
5
6
7
8
9
10
11
12
13
public class ReturnResult{
public int max;
public int min;
public boolean is;
public ReturnResult(){}
public ReturnResult(Integer mi, Integer ma, boolean is){
min = mi;
max = ma;
this.is = is;
}
}
我们定义上面的类作为节点返回值，当：
- 当前节点如果为空，直接返回null
- 当前节点所在树不是BST，is为false，最大最小值其实已经无所谓了
- 如果当前节点所在树是BST，那么返回
new ReturnResult(leftResult.min, rightResult.max, true)
这样当前节点按照左右子树返回的结果就能判断自己所在的树是不是BST了
真题链接：
判断二叉树是否是完全二叉树
思路：
- 如果当前节点有右树但没有左树，肯定不是完全二叉树
- 如果左右节点不双全，那么之后遍历到的节点都应该是叶子节点
另外这个题目不适合使用二叉树的递归套路，主要我想不到统一返回的条件，至少实现起来比较困难
求二叉树的高度
- 使用递归方法求，整棵树的高度等于左右子树的最大值+1（dfs）
- 层序遍历，二叉树的高度就是层数，注意：每次层序遍历，我们要保证当前层的所有数据都从队列中弹出，这样层次才是有效的，当队列为空时，说明每层都已经遍历完成，此时的计数遍历ans就是二叉树高度
难点在于如何让每层的数据全部从队列中弹出呢？
由于每次队列中的数据都是该层的，所以记录队列的容量size，直到size==0，说明该层的数据都已经被遍历并弹出
真题链接：
判断是否满二叉树
思路：
- 节点数N和深度l满足
N = 2^l - 1 - 左右子树应该返回给当前节点的信息中包括节点的个数和深度
判断二叉树是否为平衡二叉树
思路：
- 平衡二叉树满足的条件是：左右子树的高度差小于2
- 左右子树应该返回的信息包括：是否是平衡二叉树，高度多少
给定两个二叉树的节点Node1和Node2，找到它们的最低公共祖先节点
思路：
- Map保存所有的节点与父节点的
- 尝试保存Node1的遍历轨迹，将其保存在set集合中
- 尝试判断Node2的轨迹节点是否在Node1的set集合中，那么第一次判断在的就是它两的最低公共祖先节点
另外还有一种思路：
Node1和Node2可能出现在树中的情况：
- 如果左右子树既没有Node1也没有Node2，那么应该返回null，
- 如果左右子树返回值都不为空，那么返回当前节点，
- 如果左右子树不全为空，即一个为空一个不为空，那么返回不为空的那个
找一个节点的后继节点
后继节点就是中序遍历一个节点的后一个节点，前驱节点就是中序遍历中一个节点的前一个节点
思路：
- 遍历一遍中序，并保存，然后在里面找
第二种思路：
- 令当前节点为x，它的后继节点为y，那么当x无右树的时候判断当前节点是否是父节点的左树，是返回父节点，否则不断向上遍历
- x有右树的时候，它的后继节点是右树最左节点
二叉树的序列化和反序列化
- 二叉树序列化：将一个棵树转换成唯一的字符串
- 二叉树反序列化：将字符串还原成树
折纸问题
折痕的凹凸对应二叉树的左右树，而它的遍历序列其实就是二叉树的中序遍历