✔✨前言
🎉🎉大家好！好久不见我是青花瓷，今天你刷题了吗？文章目录,从易到难,层层递进,
本期是结合牛客101和剑指offer上面的二叉树系列OJ面试题,一起学习,一起进步。如果题解对你有帮助,点点赞支持一下,如果有错误的地方,欢迎指正✨✨
📌系列文章推荐:：
✨1.二叉树基本操作
✨2.二叉树的前中后序遍历（递归和迭代）
✨3.【Java数据结构】二叉树丶二叉树进阶——大厂经典OJ面试题——刷题笔记+做题思路
文章目录
- 二叉树刷题合集
- 打印二叉树
- 剑指 Offer 32 – I. 从上到下打印二叉树
- 剑指 Offer 32 – II. 从上到下打印二叉树 II
- 剑指 Offer 32 – III. 从上到下打印二叉树 III
- 搜索与回溯算法
- 剑指 Offer 26. 树的子结构
- 剑指 Offer 27. 二叉树的镜像
- 剑指 Offer 28. 对称的二叉树
- 搜索与回溯算法
- 剑指 Offer 34. 二叉树中和为某一值的路径
- 剑指 Offer 36. 二叉搜索树与双向链表
- 剑指 Offer 54. 二叉搜索树的第k大节点
二叉树刷题合集
打印二叉树
剑指 Offer 32 – I. 从上到下打印二叉树
OJ链接：从上到下打印二叉树
题目描述：
解题思路：
首先读懂题意，这道题就是一个 层序遍历二叉树，但是需要返回到一个数组中。
具体步骤：
- 借用 顺序表 用来存储二叉树的每个节点的值
- 借用 辅助队列 来完成二叉树的层序遍历操作
- 遍历 顺序表，将顺序表的中每个节点的 值返回到 数组中
代码如下：
class Solution {
public int[] levelOrder(TreeNode root) {
//层序遍历 一个队列 一个顺序表
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> list = new ArrayList<>();
// 如果头节点为空 返回一个 新的数组
if(root == null) return new int[0];
// 如果不为空 将元素 放入 队列中
queue.add(root);
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left != null) {
queue.add(cur.left);
}
if(cur.right != null) {
queue.add(cur.right);
}
}
int[] ret = new int[list.size()];
for(int i = 0;i < list.size();i++) {
ret[i] = list.get(i);
}
return ret;
}
}
剑指 Offer 32 – II. 从上到下打印二叉树 II
OJ链接：从上到下打印二叉树 II
题目描述：
解题思路：这道题和上一道题思路一致，只是这道题返回的是一个二维数组，简单的来说，就是在原来的一维数组上，再嵌套了一层数组，这道题需要注意几个细节，如下：
- 层序遍历 少不了 辅助 队列
- 返回二维数组，我们需要一个 二维数组接收 返回值
- 需要用 一个一维数组先去接收每一层节点的值，这里需要注意，接收每一层节点的值，需要放入循环中，确保每一层值的个数
- 具体，看代码，详细注解
代码如下：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
// 层序遍历 少不了 辅助 队列
Queue<TreeNode> queue = new LinkedList<>();
// 返回的是二位数组
List<List<Integer>> ret = new ArrayList<>();
// 一样的，先判断头节点是否为空
if(root == null) return ret;
// 不为空 root 如队列
queue.add(root);
// 循环条件
while(!queue.isEmpty()) {
// 因为我们返回的是一个二维数组，这里我们先用一维数组接收每个节点的值
List<Integer> list = new ArrayList<>();
// 这里我们要保证，每个一维数组的值，这里我们需要套上一层循环
for(int i = queue.size();i > 0;i--) {
// 弹出 队列 头部 元素,用 cur 接收
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left != null) {
queue.add(cur.left);
}
if(cur.right != null) {
queue.add(cur.right);
}
}
// 循环一次，放入一次
ret.add(list);
}
// 最后返回二维数组
return ret;
}
}
剑指 Offer 32 – III. 从上到下打印二叉树 III
OJ链接：从上到下打印二叉树 III
题目描述：
解题思路：
和上题思路一致，但是这道题说的是，偶数层，反着打印，这里我们需要做如下处理：
因为我们 返回的是 ret ，二维数组，所以，我们用 ret 的大小 去 % 2 ，如果 == 0 ，说明 是偶数层，反之，这里我们 用 双端队列来接收 每层的 节点值
代码如下：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
// 这道题和上一道题思路一样，只不过这里需要注意：
// 偶数层需要反着打印
// 这里难点就在于：反着打印是如何打印的，这里只需要在上一道题原有的基础上
// 加上一个 判断 if(ret % 2 == 0) 说明是偶数，那么就反着打印
// 这里反着打印，我们直接用双端队列的性质，双端队列底层是 LinekdList，链表
// 这里 头插 addLast 尾插 addFirst
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> ret = new ArrayList<>();
// 如果 root == null 返回 ret
if(root == null) return ret;
// 不为空 如队列
queue.add(root);
// 进入循环
while(!queue.isEmpty()) {
// 用 List 来接收 每层 节点的值
LinkedList<Integer> tmp = new LinkedList<>();
// 这里不同层数，list 接收的 节点数不同，所以我们进入循环
for(int i = queue.size();i > 0;i--) {
TreeNode cur = queue.poll();
// 加入判断,判断是 奇数层 还是 偶数层
if(ret.size() % 2 == 0) { // 说明是偶数层,反着打印，头插
tmp.addLast(cur.val);
}else {
tmp.addFirst(cur.val);
}
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
}
ret.add(tmp);
}
return ret;
}
}
搜索与回溯算法
剑指 Offer 26. 树的子结构
OJ链接：树的子结构
题目描述：
解题思路&&代码如下：
// 这道题，主要还是运用了二叉树递归的性质
// 题意给出：如果 B 是 A 的 子结构，表示 A 中有出现和B 相同结构和节点值
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
// 边界条件： 如果 A 或者 B 其中一个为空，直接返回 false;
// 因为题上给出，空数不是任意一个数的子结构
if(A == null || B == null) return false;
// 判断完边界，接下来分以下几种情况
// A 和 B 的根节点相同，依次比较它们的子节点
// 1. A 的根节点 和 B 的根节点相同，依次比较它们的子节点
// 2. A 和 B 的 根节点不同，判断 A的左子树中是否 包含 B 的根节点
// 3. A 和 B 的 根节点不同，判断 A的右子树中是否 包含 B 的根节点
return isSub(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
}
// 以下方法，实现 A 和 B 根节点相同的情况
boolean isSub(TreeNode A,TreeNode B) {
// 1. 如果遍历完 B，说明 B的全部节点都 和 A 的子结构匹配上
if(B == null) return true;
// 2. A 中的节点为 null ，B 中的节点 不为空，说明 不匹配
if(A == null) return false;
// 3. A 和 B 都不为空，但数值不同，说明不匹配
if(A.val != B.val) return false;
// 最后，当前这个点是匹配的，继续递归判断左子树和右子树，是否 分别匹配
return isSub(A.left,B.left) && isSub(A.right,B.right);
}
}
剑指 Offer 27. 二叉树的镜像
OJ链接：二叉树的镜像
题目描述：
解题思路：
先分析题目给出的 输入和输出，很明显，输入是根据二叉树的层序遍历来的，那么我们看输出，输出的图，是除了根节点以外，每一层节点都反过来了。
读懂题意，这道题就很简单了，具体步骤如下：
- 层序遍历二叉树
- 在每次入栈之后，交换左右节点的值
- 返回 根节点
代码如下：
class Solution {
public TreeNode mirrorTree(TreeNode root) {
// 层序遍历
Queue<TreeNode> queue = new LinkedList<>();
// 注意 这道题和前面的题不同，这里不需要返回二位数组，一维数组啥的，就正常的遍历就行
if(root == null) return null;
queue.add(root);
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(cur.left != null) {
queue.add(cur.left);
}
if(cur.right != null) {
queue.add(cur.right);
}
// 交换
TreeNode tmp = cur.left;
cur.left = cur.right;
cur.right= tmp;
}
return root;
}
}
剑指 Offer 28. 对称的二叉树
OJ链接：对称的二叉树
题目描述：
解题思路：
根据题意，对称二叉树，具体步骤如下：
- 如果 头节点为空 返回 true，空数也是对称的
- 判断 左右子树是否 对称
- 如何判断左右子树是否对称？具体代码如下
代码如下：
class Solution {
public boolean isSymmetric(TreeNode root) {
// 终止条件 空数也是 对称二叉树
if(root == null) return true;
// 如果 root 不等于 空 返回 辅助方法
return func(root.left,root.right);
}
// 创建个方法，判断 左右节点是否对称
boolean func(TreeNode L,TreeNode R) {
// 如果 左右节点都为空 返回TRUE
if(L == null && R == null) return true;
// 如果 左右节点一个为空，或者 左右节点 不相同
if(L == null || R == null) return false;
if(L.val != R.val) return false;
// 最后递归判断 L.left = R.right L.right = R.left
return func(L.left, R.right) && func(L.right, R.left);
}
}
搜索与回溯算法
剑指 Offer 34. 二叉树中和为某一值的路径
OJ链接：二叉树中和为某一值的路径
题目描述：
解题思路：
代码如下：
class Solution {
// DFS 深度优先搜索，用 双端队列 保存 路径
// 返回二维数组
Deque<Integer> path = new LinkedList<>();
List<List<Integer>> ret = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
DFS(root,target);
return ret;
}
public void DFS(TreeNode root,int target) {
// 1.如果头节点为null，直接返回
if(root == null) return;
// 2.不为null，放入 path 中
path.add(root.val);
// 3. target值减去 root.val的值
target -= root.val;
// 4. 如果 根节点为空，并且 target == 0，说明走完了，将走完的路径放入 ret 中
if(root.left == null && root.right == null && target == 0) {
// 这里不能直接 ret.add(path)，如果这样 ret 会随 path 的变化而变化，
// 这里的操作是复制了 path
ret.add(new LinkedList<>(path));
}
// 5. 如果都没有满足，继续搜索
DFS(root.left,target);
DFS(root.right,target);
// 6. 如果 加入的值，超出了范围
path.pollLast();
}
}
剑指 Offer 36. 二叉搜索树与双向链表
OJ链接：二叉搜索树与双向链表
题目描述：
解题思路&&代码如下：
class Solution {
// 根据题意得：二叉搜索树，左节点 < 根节点 < 右节点 -》 中序遍历
Node pre,head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
DFS(root);
// 首尾相连
pre.right = head;
head.left = pre;
return head;
}
// DFS 搜素每个节点，并将每个节点 相连
public void DFS(Node cur) {
if(cur == null) return;
// 中序遍历
DFS(cur.left);
// 这里需要判断一下，如果pre 为空，说明 head，为头节点
if(pre == null) {
head = cur;
}else {
// 如果不为空,建立链接
pre.right = cur;
}
cur.left = pre;
pre = cur;
DFS(cur.right);
}
}
剑指 Offer 54. 二叉搜索树的第k大节点
OJ链接：二叉搜索树的第k大节点
题目描述：
解题思路&&代码如下：
class Solution {
// 核心思路：二叉搜索树，中序遍历为递增
// 那么如果我们反着来 就为递减，在加入 计数器，没遍历一个节点计数器++
// 直到计数器 == k
// 用 ret 接收 返回值
int count;
int ret;
public int kthLargest(TreeNode root, int k) {
DFS(root,k);
return ret;
}
void DFS(TreeNode root,int k) {
if(root == null) return;
DFS(root.right,k);
count++;
if(count == k) ret = root.val;
DFS(root.left,k);
}
}
文章出处登录后可见！
已经登录？立即刷新
