树
其实，树相关的题是我觉得应该第一个刷的，刷树相关的题目，可以很好的培养我们的递归思维和增加我们对指针操作的熟练度，为我们之后的算法学习，打下一个坚实的基础。
在刷树的相关题目之前，我们先把树的数据结构熟悉一下（这里的树，统一为二叉树，如果是多叉树我们再另说）
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {}
public TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
一、树的递归
104 - 二叉树的最大深度
题目
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
思考
树的递归，分为深度优先和广度优先
使用广度优先，我们必须要借助数据结构 队列，需要开辟额外的空间，这是我们不希望发生的
而是用深度优先，我们除了可以使用栈以外，还可以使用递归
因为完全遍历一个树的时间复杂度是 O(n)，所以说，两个方法我们选其中空间复杂度小的，即使用 DFS
这里还要多提一句，在实际生产环境中，我们还是建议使用栈来替代递归，一是因为递归一旦出错，难以排错；二是因为递归深度一旦较大，就有出现栈溢出异常的风险
题解
这道题，各位一定要牢牢掌握
这可以说是二叉树中最经典的题目了
如果记不住，背也要把它背下来
public int maxDepth(TreeNode root) {
if (root==null) return 0;
return recursion(root,0,Integer.MIN_VALUE);
}
public int recursion(TreeNode root,int depth,int max) {
// 递归终止条件
// 在终止判断之前，我们还需要比较当前深度与之前记录的最大深度
if (root==null) {
if (depth>max) {
max=depth;
}
return max;
}
int lMax=recursion(root.left,depth+1,max);
int rMax=recursion(root.right,depth+1,max);
return Math.max(lMax,rMax);
}
写成上面那样，只是为了让各位看得清楚一点
其实，这道题完全可以进行写成一行代码的骚操作：
public int maxDepth(TreeNode root) {
return root==null ? 0 : Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1);
}
110 - 平衡二叉树
题目
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
思考
我们的第一反应，肯定是找到树的最大深度和最小深度，如果最大最小深度差值不超过1，说明整棵树肯定是平衡的，反之则不平衡
但是，这种方法，需要进行两次遍历，才能得出结果，明显不是我们希望的
我们其实可以采取分治的思想，将问题由大化小
一颗子树，如果其左子树和右子树最长边的高度差，如果不大于1，则当前子树是符合规范的
但是前提是，该子树的子树，直到叶子节点，也都必须是合乎规范的
基于这个逻辑，我们就可以编写出递归的代码
题解
public boolean isBalanced(TreeNode root) {
return recursion(root)==-1?false:true;
}
public int recursion(TreeNode root) {
if (root==null) return 0;
int lMax = recursion(root.left);
int rMax = recursion(root.right);
// 如果当前子树不符合规范，直接返回-1，达到剪枝的效果
if (lMax==-1 || rMax==-1 || Math.abs(lMax-rMax)>1) return -1;
// 这里的 +1，可以理解为把当前层加上去
return Math.max(lMax,rMax)+1;
}
543 - 二叉树的直径
题目
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
思考
这道题看似唬人，其实，将问题转换一下，就是找出左子树最大深度和右子树最大深度之和最大的节点
这里我们要注意，二叉树直径长度，是比路径长度小1的，这通过观察二叉树的数据结构可以看出来
所以，如果我们找到的是路径长度的话，最后的直径长度要在路径长度的基础上减1
题解
在做这道题的时候，我们不得不去使用一个全局变量
如果是 c++ 玩家的话，可以用引用变量区避免这个问题
java 玩家，其实也可以自己设计一个类，去包装这个参数
这里，我还是使用一个全局变量
private int max;
public int diameterOfBinaryTree(TreeNode root) {
recursion(root);
// 我们要求的是直径，不是路径长度
return max-1;
}
public int recursion(TreeNode root) {
if (root==null) return 0;
int lMax = recursion(root.left);
int rMax = recursion(root.right);
if (lMax+rMax+1>max) max=lMax+rMax+1;
/**
* 返回当前子树最长的边
* 这里 +1,是为了加上当前的层
*/
return Math.max(lMax,rMax)+1;
}
101 - 对称二叉树
题目
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
思考
我们可以先找一个符合题意的镜像二叉树的特例
就拿 例子1 举例吧
我们对它进行中序遍历，可以发现，遍历顺序是 3,2,4,1,4,2,3，也是对称的，这就衍生出我们的第一个思路，即对二叉树进行中序遍历，记录遍历的节点，然后判断记录下来的节点是否是回文的
但是这种方法毕竟还是需要开辟额外的空间，第二种方法，我们尝试使用递归，题解我们也用递归去写
题解
public boolean isSymmetric(TreeNode root) {
return root==null?true:recursion(root.left,root.right);
}
public boolean recursion(TreeNode left,TreeNode right) {
if (left==null && right==null) return true;
if (left==null || right==null) return false;
if (left.val != right.val) return false;
// 这里要注意，因为是镜像的，所以要注意对比的节点的匹配
return recursion(left.left,right.right) &&
recursion(left.right,right.left);
}
226 - 翻转二叉树
My personal favourite
关于这道题，有个小故事，macos 最泛用的程序–homebrew 的作者去应聘 google 的职位，但是因为写不出翻转二叉树的代码，最后被面试官当场怼了
那我们就来看看，这个让大佬也为难的题目，究竟长什么样子
题目
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
思考
我们我们可以让左右子树交换
然后左右子树在进行递归反转
（当然，这个顺序反过来也无所谓）
题解
public TreeNode invertTree(TreeNode root) {
if (root==null) return root;
// 翻转
recursion(root);
return root;
}
public void recursion(TreeNode root) {
if (root==null) return;
recursion(root.left);
recursion(root.right);
TreeNode tmp = root.left;
root.left=root.right;
root.right=tmp;
}
有同学可能会说了：“我这到很快就 AC 了，能去 google 了吗？”
骚年，你还差写一个 homebrew 出来 : )
二、树的层次遍历
103 - 二叉树的锯齿形层次遍历
这道题可是经典字节题
字节跳动特别喜欢考这题
题目
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
思考
还是层次遍历
还是要记录每层的信息
区别在于，我们这里还要记录层数
奇数层从左往右遍历
偶数层从右往左遍历
题解
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root==null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int lay = 1;
while (!queue.isEmpty()) {
List<Integer> rowList = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode tmp = queue.poll();
if (tmp.left!=null) queue.offer(tmp.left);
if (tmp.right!=null) queue.offer(tmp.right);
rowList.add(tmp.val);
}
// 如果是偶数层的话，需要反转
if (lay%2==0) Collections.reverse(rowList);
lay++;
res.add(rowList);
}
return res;
}
637 - 二叉树的层平均值
题目
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
示例 1：
输入：
3
/ \
9 20
/ \
15 7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
思考
这道题要求我们在做到层次遍历的同时，还要记录每层的数据
想要实现这个效果，是有套路的：
1、使用队列进行存储层次遍历信息
2、每次在进行队列非空判断之前，都要先记录下队列的大小，这个大小，就是当前层的节点个数
题解
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if (root==null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 要记录队列的长度，因为这是当前层的节点个数
int size = queue.size();
// 用来存储当前层的所有节点的值的和
Double sum = 0d;
for (int i = 0; i < size; i++) {
TreeNode tmp = queue.poll();
sum+=tmp.val;
if (tmp.left!=null) queue.offer(tmp.left);
if (tmp.right!=null) queue.offer(tmp.right);
}
res.add(Double.valueOf(sum/size));
}
return res;
}
二叉树的层次遍历方法，一定要牢记，很多地方都会用到的
三、二叉树的前中后序遍历
前中后序的遍历是二叉树最最基础的内容，我在这里就不过多赘述了
感兴趣的小伙伴，可以上网查找相关信息
144 - 二叉树的前序遍历
我们先来看一看，二叉树的前序遍历是个什么样子的
题目
前序遍历应该都知道是什么吧？
我这里就不放题目了
思考
递归的版本想必大家都熟悉
这里，我们要尝试不使用迭代
使用迭代要注意节点入栈的顺序
题解
- 递归版
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
preOrderRecurson(root,list);
return list;
}
public void preOrderRecurson(TreeNode root,List<Integer> list) {
if (root==null) return;
list.add(root.val);
preOrderRecurson(root.left,list);
preOrderRecurson(root.right,list);
}
- 非递归版
使用栈，可以实现非递归的前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root==null) return res;
LinkedList<TreeNode> stack = new LinkedList<>();
stack.addLast(root);
while (!stack.isEmpty()) {
TreeNode tmp = stack.removeLast();
res.add(tmp.val);
// 我们想实现的是前序遍历，那栈里面要先放右，再放左
if (tmp.right!=null) stack.addLast(tmp.right);
if (tmp.left!=null) stack.addLast(tmp.left);
}
return res;
}
105 - 使用前序与中序遍历序列构造二叉树
题目
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
思考
二叉树中，我最讨厌的类型，就是根据不同序列构造二叉树这类题了
解题思路我也不想写了，就放一个别人的吧
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/dong-hua-yan-shi-105-cong-qian-xu-yu-zhong-xu-bian/
这个思路不是最优解，因为需要开辟额外空间，其实还有更优的解法
但是，这个思路是最容易想，也最不容易出错的，因为最优解的思路，函数形参超级多，写着写着脑袋就晕了
题解
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length==0 || inorder.length==0) return null;
// 前序序列的第一个元素，一定是整棵树的根节点
TreeNode root = new TreeNode(preorder[0]);
for (int i = 0; i < inorder.length; i++) {
/**
* 找到中序遍历中，根节点的位置
* 此时，i 就是左子树的长度
* inorder.length - (i+1) 就是右子树的长度
*/
if (preorder[0]==inorder[i]) {
int[] pre_left = Arrays.copyOfRange(preorder, 1, i+1);
int[] pre_right = Arrays.copyOfRange(preorder, i + 1, preorder.length);
int[] in_left = Arrays.copyOfRange(inorder, 0, i);
int[] in_right = Arrays.copyOfRange(inorder, i + 1, inorder.length);
root.left=buildTree(pre_left,in_left);
root.right=buildTree(pre_right,in_right);
break;
}
}
return root;
}
四、二叉查找树
二叉查找树(Binary Search Tree, BST)是一种特殊的二叉树：
对于每个父节点，其左子节点 的值小于等于父结点的值，其右子节点的值大于等于父结点的值。因此对于一个二叉查找树，我 们可以在 O(n log n) 的时间内查找一个值是否存在。从根节点开始，若当前节点的值大于查找值 则向左下走，若当前节点的值小于查找值则向右下走。同时因为二叉查找树是有序的，对其中序遍历的结果即为排好序的数组（这一性质，经常是解二叉搜索树相关题目的关键）。
99 - 恢复二叉搜索树（未完成）
题目
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
**进阶：**使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
示例 1：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
思考
要做这道题，我们可以先看看有序数组中，两个值被调换位置，是个什么情况：
- 非相邻位置
我们交换 2 和 6 两个数
原：1,2,3,4,5,6,7
换：1,6,3,4,5,2,7
我们发现，会出现 6>3，5>2两个异常位置
- 相邻位置
我们交换 3 和 4 两个数
原：1,2,3,4,5,6,7
换：1,2,4,3,5,6,7
可以发现，相邻位置数字交换，只会出现一个异常位
这样我们就可以思考解题方法了：
中序遍历整个树，找到两个
题解
这道题我就不写了，留给各位做思考题。
669 - 修剪二叉搜索树
题目
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
示例 1：
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
示例 3：
输入：root = [1], low = 1, high = 2
输出：[1]
示例 4：
输入：root = [1,null,2], low = 1, high = 3
输出：[1,null,2]
示例 5：
输入：root = [1,null,2], low = 2, high = 4
输出：[2]
思考
如果光看题目描述，这道题确实很难看懂
但是有那两张图，就一目了然了
我们还是进行中序遍历
当遍历到某个节点 node
如果 node 的左节点值小于 low，舍弃左节点
如果 node 的右节点值大于 high，舍弃右节点
因为有 图2 那种情况
我们还需要在剪左节点的时候，考虑左节点的右子树
在剪右节点的时候，考虑右节点的左子树
题解
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root==null) return null;
// 如果当前节点的值小于 low ，结果肯定在右枝出现
if (root.val<low) return trimBST(root.right,low,high);
// 如果当前节点的值大于 high ，结果肯定在左枝出现
if (root.val>high) return trimBST(root.left,low,high);
root.left=trimBST(root.left,low,high);
root.right=trimBST(root.right,low,high);
return root;
}
五、字典树
字典树(Trie)用于判断字符串是否存在或者是否具有某种字符串前缀。
如果有大量的英文单词存储请求，使用字典树，可以极大的压缩存储空间，并且查找的时间复杂度是 O(N)<N是英文单词的平均长度>
208 - 实现 Tire Tree
题目
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
思考
其实就是个字典树，题中说了word 和 prefix 仅由小写英文字母组成，所以我们还可以把它看做是一颗26叉树，也就是说每个节点最多有26个子节点
题解
这道题，就作为各位的思考题了