本篇总结主要来源于https://labuladong.gitee.io/algo/]
二叉树递归遍历框架
二叉树的遍历分为前中后序三种，这三种遍历方式分别代表遍历二叉树过程中处理每个结点的三个特殊时间点：
- 前序位置的代码在刚进入一个二叉树节点的时候执行；
- 后序位置的代码在将要离开一个二叉树节点的时候执行；
- 中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。
二叉树遍历框架：
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序位置
traverse(root.left);
// 中序位置
traverse(root.right);
// 后序位置
}
eg: 在二叉树中搜索target：
TreeNode search(TreeNode root, int target);
if (root == null) return null;
if (root.val == target) return root;
// 当前节点没找到就递归地去左右子树寻找
TreeNode left = search(root.left, target);
TreeNode right = search(root.right, target);
return left != null ? left : right;
}
在解题过程中，你只需要知道每个节点应该做什么，在什么时候做，然后根据函数定义，选择合适的位置，通过二叉树遍历框架，递归调用子节点，递归会对所有节点做相同的操作。
注意：
有时候我们需要设置辅助函数，增加函数参数列表，在参数中携带额外的信息，将这种约束传递给子树的所有节点。
二叉树题目思路
关于应该做什么，通常来说有两种思路：①遍历一遍二叉树得出答案；②分解子问题，通过计算得到答案。
eg ：力扣104题 二叉树的最大深度，最大深度就是根节点到最远叶子节点的路径上的节点数，两种思路都可以解决。
思路①遍历一遍二叉树得出答案：可以遍历一遍二叉树，用一个外部变量记录每个节点所在的深度，取最大值就可以得到二叉树的最大深度。
// 记录最大深度
int res = 0;
// 记录遍历到的节点的深度
int depth = 0;
// 主函数
int maxDepth(TreeNode root) {
traverse(root);
return res;
}
// 二叉树遍历框架
void traverse(TreeNode root) {
if (root == null) {
// 到达叶子节点，更新最大深度
res = Math.max(res, depth);
return;
}
// 前序位置，进入一个节点
depth++;
traverse(root.left);
traverse(root.right);
// 后序位置，离开一个节点
depth--;
}
思路②分解子问题，通过计算得到答案：二叉树的最大深度也可以通过子树的最大高度+1计算出来。
// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 利用定义，计算左右子树的最大深度
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 整棵树的最大深度等于左右子树的最大深度取最大值，
// 然后再加上根节点自己
int res = Math.max(leftMax, rightMax) + 1;
return res;
}
综上，遇到一道二叉树题，可以这样思考：是否可以通过遍历一遍二叉树得到答案？如果不能，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？
二叉树题解时机
关于在什么时候做，如前文所述，处理二叉树结点有三个时间点：前、中、后，不同时间点由于其所处位置的特性不同，处理问题的效果也不尽相同。
前序位置为刚刚进入节点的时刻，意味着前序位置的代码只能从函数参数中获取父节点传递来的数据。
- 前序位置本身其实没有什么特别的性质，之所以你发现好像很多题都是在前序位置写代码，实际上是因为我们习惯把那些对前中后序位置不敏感的代码写在前序位置。
中序位置在左子树遍历完，开始遍历右子树的时刻，意味着中序位置不仅可以获取父节点传递来的参数，调整左右子树遍历顺序，还可以获取到左子树或右子树通过函数返回值传递回来的数据。
- 中序位置主要用在二叉搜索树（BST ）场景中，鉴于BST‘左小右大’的性质，BST 的中序遍历相当于遍历有序数组，可以升序或降序遍历BST。
后序位置为离开节点的时刻，意味着后续位置的代码不仅可以获取父节点传递来的参数数据，还可以获取到左右子树通过函数返回值传递回来的数据。
- 由于递归利用了堆栈先进后出的性质，二叉树递归遍历，前序位置的代码执行是自顶向下的，而后序位置的代码执行是自底向上的。
- 当题目需要用到左右子树函数的返回值，那大概率要给函数设置合理的定义和返回值，在后序位置写代码。很多时候通过后续位置获取左右子树的返回值可以少写很多步骤，提高运行效率。
eg：力扣543题 二叉树的直径，二叉树的直径长度就是任意两个节点之间的路径长度，最长直径并不一定要穿过根节点。
思路：每一条二叉树的直径长度就是一个节点的左右子树的最大深度之和，最直接的就是遍历整棵树中每个节点，通过求出每个节点的左右子树的最大深度之和算出每个节点的直径，然后比较得到最大直径即可。
// 记录最大直径的长度
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
// 对每个节点计算直径，求最大直径
traverse(root);
return maxDiameter;
}
// 遍历二叉树
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 对每个节点计算直径
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
int myDiameter = leftMax + rightMax;
// 更新全局最大直径
maxDiameter = Math.max(maxDiameter, myDiameter);
traverse(root.left);
traverse(root.right);
}
// 计算二叉树的最大深度
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
return 1 + Math.max(leftMax, rightMax);
}
这个解法递归函数traverse遍历每个节点时都会调用递归函数maxDepth遍历子树的所有节点，最坏的时间复杂度为O(N^2)。traverse中，在前序位置无法获取子树信息，得到左右子树最大深度，只能让每个节点都调用maxDepth函数去计算子树的深度。而我们发现，在maxDepth函数中已经算出了左右子树的最大深度，那么只需要在maxDepth函数的后序位置通过已知的左右子树深度算出直径，通过比较即可得到最大直径。
改良：
// 记录最大直径的长度
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return maxDiameter;
}
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 后序位置顺便计算最大直径
int myDiameter = leftMax + rightMax;
maxDiameter = Math.max(maxDiameter, myDiameter);
return 1 + Math.max(leftMax, rightMax);
}
改良后，时间复杂度只有maxDepth函数的O(N)了。
综上：遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。如果写出了递归套递归的解法，大概率需要反思是不是可以通过后序遍历优化。
二叉树的层序（迭代）遍历
// 输入一棵二叉树的根节点，层序遍历这棵二叉树
void levelTraverse(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// 从上到下遍历二叉树的每一层
while (!q.isEmpty()) {
int sz = q.size();
// 从左到右遍历每一层的每个节点
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 将下一层节点放入队列
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}
}
经典试题
力扣 105. 从前序与中序遍历序列构造二叉树
力扣 106. 从中序与后序遍历序列构造二叉树
力扣 889. 根据前序和后序遍历构造二叉树
本次就只讲解从前序与中序遍历序列构造二叉树，另外两题思路差不多（以前写过好像）。
我们先来回顾一下前序遍历和中序遍历：
解决本题需要考虑：①如何得到根节点，②如何确定左右子树。然后通过递归对每个结点做相同的事，最终构造出整棵二叉树。
①如何找到根节点：前序遍历的第一个值 preorder[0] 就是根节点的值。
②如何确定左右子树：前序序列获得根节点值，在中序序列找到根节点所在的索引下标index,index两端分别是左右子树，即可得到左右子树的前序序列和中序序列。
解法代码：
TreeNode build(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
//序列为空
if (preStart > preEnd) {
return null;
}
// root 节点对应的值就是前序遍历数组的第一个元素
int rootVal = preorder[preStart];
// rootVal 在中序遍历数组中的索引
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
int leftSize = index - inStart;
// 先构造出当前根节点
TreeNode root = new TreeNode(rootVal);
// 递归构造左右子树
root.left = build(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftSize + 1, preEnd,
inorder, index + 1, inEnd);
return root;
}
而从中序和后序序列构造二叉树思路相同，只不过后序遍历和前序遍历相反，根节点对应的值为 postorder 的最后一个元素。
通过前序或者后序遍历结果找到根节点，然后在根据中序遍历结果确定左右子树，所以你可以通过前序中序，或者后序中序遍历结果可以唯一确定一棵原始二叉树，但是通过前序后序遍历结果无法确定原始二叉树。因为遍历结果没有记录空的左右子节点，你可以确定根节点，但是无法确切的知道左右子树有哪些节点。
eg：根据前后序序列构造二叉树中，我们假设前序遍历的第二个元素是左子树的根节点，但实际上左子树可能是空指针，这个元素可能是右子树的根节点。由于这里无法确切进行判断，所以导致了最终答案的不唯一。
