力扣剑指offer——二叉树篇

news/2024/11/8 9:40:00/

✔✨前言

🎉🎉大家好！好久不见我是青花瓷，今天你刷题了吗？文章目录,从易到难,层层递进,本期是结合牛客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链接：从上到下打印二叉树

题目描述：

在这里插入图片描述
解题思路：

首先读懂题意，这道题就是一个 层序遍历二叉树，但是需要返回到一个数组中。

具体步骤：

  1. 借用 顺序表 用来存储二叉树的每个节点的值
  2. 借用 辅助队列 来完成二叉树的层序遍历操作
  3. 遍历 顺序表，将顺序表的中每个节点的 值返回到 数组中

代码如下：

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

题目描述：

在这里插入图片描述

解题思路：这道题和上一道题思路一致，只是这道题返回的是一个二维数组，简单的来说，就是在原来的一维数组上，再嵌套了一层数组，这道题需要注意几个细节，如下：

  1. 层序遍历 少不了 辅助 队列
  2. 返回二维数组，我们需要一个 二维数组接收 返回值
  3. 需要用 一个一维数组先去接收每一层节点的值，这里需要注意，接收每一层节点的值，需要放入循环中，确保每一层值的个数
  4. 具体，看代码，详细注解

代码如下：

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 尾插 addFirstQueue<TreeNode> queue = new LinkedList<>();List<List<Integer>> ret = new ArrayList<>();// 如果 root == null 返回 retif(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链接：二叉树的镜像

题目描述：

在这里插入图片描述
解题思路：

先分析题目给出的 输入和输出，很明显，输入是根据二叉树的层序遍历来的，那么我们看输出，输出的图，是除了根节点以外，每一层节点都反过来了。

读懂题意，这道题就很简单了，具体步骤如下：

  1. 层序遍历二叉树
  2. 在每次入栈之后，交换左右节点的值
  3. 返回 根节点

代码如下：

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链接：对称的二叉树

题目描述：

在这里插入图片描述
解题思路：

根据题意，对称二叉树，具体步骤如下：

  1. 如果 头节点为空 返回 true，空数也是对称的
  2. 判断 左右子树是否 对称
  3. 如何判断左右子树是否对称？具体代码如下

代码如下：

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) {// 如果 左右节点都为空 返回TRUEif(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.leftreturn 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 的变化而变化，// 这里的操作是复制了 pathret.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);}
}

http://www.ppmy.cn/news/814075.html

相关文章

电容笔和Apple pencil区别有什么？双十一值得入手的电容笔推荐

电容笔和Apple pencil区别有什么？双十一值得入手的电容笔推荐

普通电容笔和Apple Pencil最大的不同之处就是&#xff0c;普通电容笔没有Apple Pencil特有的重力压感&#xff0c;只会让人感觉到一种倾斜的压感&#xff0c;但是对于不懂画画的人来说&#xff0c;这种重力压感就不太需要&#xff0c;其实普通电容笔的其他方面和Apple Pencil一…
阅读更多...
qt 闹钟实现

qt 闹钟实现

实现一个闹钟 自定义时间 按下开始后 开始计时&#xff0c;结束计时会播报语音 widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTimer> #include <QTimerEvent> #include <QDateTime> #include <QTime> #include …
阅读更多...
ps钢笔工具的详细讲解

ps钢笔工具的详细讲解

本文转自&#xff1a;http://blog.sina.com.cn/s/blog_6e1dc1080100nm7z.html&#xff0c;感谢作者分享&#xff01; 首先来简要介绍一下钢笔工具和路径的概念 1、钢笔工具属于矢量绘图工具&#xff0c;其优点是可以勾画平滑的曲线&#xff0c;在缩放或者变形之后仍能保持平滑效…
阅读更多...
PS使用技巧（四） 钢笔尖 P 直接选择工具 A

PS使用技巧（四） 钢笔尖 P 直接选择工具 A

钢笔尖工具&#xff0c;操作锚点和手柄的形式绘制图形&#xff0c;然而直接选择工具&#xff0c;是将绘制的锚点和手柄进行修改。 钢笔尖在前端的应用中&#xff0c;很少能涉及到&#xff0c;但是得知道&#xff0c;偶尔画个小图标&#xff0c;或者偶尔修改个形状都能用到&…
阅读更多...
indesign如何画弧线_钢笔工具怎么绘制弧线?AI钢笔工具用法全解

indesign如何画弧线_钢笔工具怎么绘制弧线?AI钢笔工具用法全解

ai中的钢笔工具是我们经常需要用到的&#xff0c;并且也是一个重要的难点&#xff0c;尤其对于新手来说&#xff0c;更不知道怎么操作&#xff0c;那么钢笔工具怎么绘制弧线?下面小编就为大家介绍AI钢笔工具用法&#xff0c;希望对学习钢笔工具的朋友有所帮助。 下面就一起来看…
阅读更多...
LeetCode-外观数列【小名带你解读LeetCode第38题-外观数列 的题目！最清晰的题解】

LeetCode-外观数列【小名带你解读LeetCode第38题-外观数列 的题目！最清晰的题解】

一道读题读到懵的题目&#xff0c;通过这题&#xff0c;我发现&#xff0c;我不止是算法差&#xff0c;语文更差&#xff01;嗯&#xff01;很多题不是不会&#xff01;而是我没有读懂题&#xff01;没错&#xff01;就是这个原因&#xff01;&#x1f602; 题目&#xff1a; …
阅读更多...
哪个电容笔是主动式？好用不贵电容笔测评

哪个电容笔是主动式？好用不贵电容笔测评

主动式电容笔和被动式电容笔最大的区别是&#xff0c;主动电容笔可以更好的控制屏幕&#xff0c;能适用于一切的电容式显示屏。如今&#xff0c;人们对电容笔的了解日益加深&#xff0c;人们也逐渐地采用了它。为了获得更好的使用效果&#xff0c;电容笔可以采用平替电容笔&…
阅读更多...
触屏笔和电容笔哪个好？非常值得入手的电容笔推荐

触屏笔和电容笔哪个好？非常值得入手的电容笔推荐

我们是否要在IPAD买完后再去买苹果的Pencil&#xff1f;事实上&#xff0c;就算是画画&#xff0c;也不需要用到苹果笔。除了Apple Pencil&#xff0c;目前也有大量的平替电容笔。用来做日常的记录和记录&#xff0c;都是非常有用的。而且平替的电容笔&#xff0c;在价格上会实…
阅读更多...
最新文章

Copyright @ 2022~2023