当前位置:网站首页>力扣剑指offer——二叉树篇
力扣剑指offer——二叉树篇
2022-07-05 01:36:00 【偷偷敲代码的青花瓷】
前言
大家好!好久不见我是青花瓷,今天你刷题了吗?文章目录,从易到难,层层递进,
本期是结合牛客101和剑指offer上面的二叉树系列OJ面试题
,一起学习,一起进步。如果题解对你有帮助,点点赞支持一下,如果有错误的地方,欢迎指正
系列文章推荐::
1.二叉树基本操作
2.二叉树的前中后序遍历(递归和迭代)
3.【Java数据结构】二叉树丶二叉树进阶——大厂经典OJ面试题——刷题笔记+做题思路
文章目录
二叉树刷题合集
打印二叉树
剑指 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);
}
}
边栏推荐
- Global and Chinese market of optical densitometers 2022-2028: Research Report on technology, participants, trends, market size and share
- Phpstrom setting function annotation description
- Classification of performance tests (learning summary)
- Win:使用 PowerShell 检查无线信号的强弱
- Application and Optimization Practice of redis in vivo push platform
- Yyds dry inventory jetpack hit dependency injection framework Getting Started Guide
- [development of large e-commerce projects] performance pressure test - Optimization - impact of middleware on performance -40
- JS implementation determines whether the point is within the polygon range
- Kibana installation and configuration
- 线上故障突突突?如何紧急诊断、排查与恢复
猜你喜欢
To sort out messy header files, I use include what you use
【LeetCode】88. Merge two ordered arrays
[OpenGL learning notes 8] texture
How to safely eat apples on the edge of a cliff? Deepmind & openai gives the answer of 3D security reinforcement learning
Async/await you can use it, but do you know how to deal with errors?
The perfect car for successful people: BMW X7! Superior performance, excellent comfort and safety
Wechat applet: independent background with distribution function, Yuelao office blind box for making friends
流批一体在京东的探索与实践
Redis master-slave replication cluster and recovery ideas for abnormal data loss # yyds dry goods inventory #
Remote control service
随机推荐
Nebula importer data import practice
Global and Chinese markets of emergency rescue vessels (errv) 2022-2028: Research Report on technology, participants, trends, market size and share
Wechat applet: exclusive applet version of the whole network, independent wechat community contacts
Basic operations of database and table ----- create index
微信小程序:全新独立后台月老办事处一元交友盲盒
Database postragesq peer authentication
Es uses collapsebuilder to de duplicate and return only a certain field
[wave modeling 2] three dimensional wave modeling and wave generator modeling matlab simulation
Wechat applet: independent background with distribution function, Yuelao office blind box for making friends
Expansion operator: the family is so separated
One plus six brushes into Kali nethunter
Win: add general users to the local admins group
PHP 基础篇 - PHP 中 DES 加解密详解
Main window in QT application
19. Delete the penultimate node of the linked list
[swagger]-swagger learning
[wave modeling 1] theoretical analysis and MATLAB simulation of wave modeling
【CTF】AWDP总结(Web)
The server time zone value ‘� й ��� ʱ 'is unrecognized or representatives more than one time zone【
【大型电商项目开发】性能压测-优化-中间件对性能的影响-40