Leetcode二叉树部分笔记

news/2024/12/15 10:56:38/

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

Leetcode二叉树部分笔记

  • 1.二叉树的最大深度
  • 2.同样的树
  • 3.翻转二叉树
  • 4.对称二叉树
  • **5. **填充每个节点的下一个右侧节点指针 II**
  • 6. 二叉树展开为链表
  • 7. 路经总和
  • 8.完全二叉树的节点个数


1.二叉树的最大深度

给定一个二叉树 root ,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
在这里插入图片描述
**解题思路:**如果用广度优先遍历的话,设置一个队列,quque.offer代表让节点进入队列,判断当前队列内还有没有值,如果有则把它的左右孩子放进来,并把size–,每清空一次队列,代表遍历了一层,建一个计数器每遍历一层,计数器加一。最终得到深度。

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);int ans = 0;while (!queue.isEmpty()) {int size = queue.size();while (size > 0) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}size--;}ans++;}return ans;}
}

**解题思路2:**使用深度优先遍历,采用递归:假设深度优先到最后一层,执行这个函数,左孩子为null,右孩子为null,左孩子执行这个函数,返回0,右孩子执行这个函数,也返回0。该节点返回1,它的上一层 leftHeight就成1了。同理,如果他的上一层没有右孩子,则右孩子返回0,则这个上一层返回2。以此类推。

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}
}

2.同样的树

给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

在这里插入图片描述
**解题思路:**使用深度优先遍历。假设p和q都到了最后一层,p,left == null,q.left ==null,因此函数返回true,同理p.right == null 并且q.right == null,同样返回true,这样该节点返回一个true,返回给上一层,看看第一层是不是都是true。

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p==null && q==null){return true;}else if(p==null || q==null){return false;}else if(p.val != q.val){return false;}else{return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}}
}

3.翻转二叉树

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
在这里插入图片描述
解题思路:假设在最后一层的两个节点,这两个节点的四个孩子都是null,返回他们本身就可以,这两个节点的上一层的父节点,接收到下面返回上来的left和right,并对这两个进行置换,把它自身返回上去,以此类推。

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.left = right;root.right = left;return root;}
}

4.对称二叉树

给你一个二叉树的根节点 root , 检查它是否轴对称。
在这里插入图片描述
**解题思路:**也就是判断L.left和R.right 以及 L.right = R.left,是否都能同时到达最底部,如果没有则说明不对称。

class Solution {public boolean isSymmetric(TreeNode root) {return root == null || recur(root.left, root.right);}boolean recur(TreeNode L, TreeNode R) {if (L == null && R == null) return true;if (L == null || R == null || L.val != R.val) return false;return recur(L.left, R.right) && recur(L.right, R.left);}
}作者:Krahets
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

**5. 填充每个节点的下一个右侧节点指针 II

给定一个二叉树:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL 。

在这里插入图片描述

**解题思路:**层序遍历,设置一个指针,如果当前层的大小不为1,则说明后面还有,让这个指针的next指向poll出来的节点,再让指针更新,如果大小为1,则不做任何操作。

class Solution {public Node connect(Node root) {if (root == null) {return null;}Queue<Node> queue = new LinkedList<Node>();queue.offer(root);while (!queue.isEmpty()) {int n = queue.size();Node last = null;for (int i = 1; i <= n; ++i) {Node f = queue.poll();if (f.left != null) {queue.offer(f.left);}if (f.right != null) {queue.offer(f.right);}if (i != 1) {last.next = f;}last = f;}}return root;}
}

6. 二叉树展开为链表

给你二叉树的根结点 root ,请你将它展开为一个单链表:

展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
在这里插入图片描述

**解题思路:**设置一个pre,专门寻找root节点的left孩子的最右侧孩子,到达最右侧后让最右侧的右指针指向root的右孩子,让root的右指针指向root的左孩子,再让root向下走,遍历一遍。

class Solution {public void flatten(TreeNode root) {while (root != null) { //左子树为 null,直接考虑下一个节点if (root.left == null) {root = root.right;} else {// 找左子树最右边的节点TreeNode pre = root.left;while (pre.right != null) {pre = pre.right;} //将原来的右子树接到左子树的最右边节点pre.right = root.right;// 将左子树插入到右子树的地方root.right = root.left;root.left = null;// 考虑下一个节点root = root.right;}}
}

7. 路经总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

叶子节点 是指没有子节点的节点。
在这里插入图片描述
**解题思路:**假设在最后一层,发现root.left == null && root.right ==null 则返回当前value和sum值是否相等的判断,如果相等,则说明成立,直接返回true,如果不相等则返回false。

class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) {return false;}if (root.left == null && root.right == null) {return sum == root.val;}return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);}
}

8.完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。

class Solution {public int countNodes(TreeNode root) {if(root == null) {return 0;}int left = countNodes(root.left);int right = countNodes(root.right);return left+right+1;}
}

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

相关文章

.NET平台使用C#设置Excel单元格数值格式

设置Excel单元格的数字格式是创建、修改和格式化Excel文档的关键步骤之一&#xff0c;它不仅确保了数据的正确表示&#xff0c;还能够增强数据的可读性和专业性。正确的数字格式可以帮助用户更直观地理解数值的意义&#xff0c;减少误解&#xff0c;并且对于自动化报告生成、财…

yolov8 转华为昇腾om脚本

目录 yolov8 转华为昇腾 om脚本 测试ok 推理demo: yolov8 转华为昇腾 om脚本 测试ok import sys import osos.chdir(os.path.dirname(os.path.abspath(__file__)))import torchcurrent_dir = os.path.dirname(os.path.abspath(__file__))paths = [os.path.abspath(__file__)…

基于 SSM 的校园一卡通密钥加密传输机制与安全性能提升

第4章 系统设计 市面上设计比较好的系统都有一个共同特征&#xff0c;就是主题鲜明突出。通过对页面简洁清晰的布局&#xff0c;让页面的内容&#xff0c;包括文字语言&#xff0c;或者视频图片等元素可以清晰表达出系统的主题。让来访用户无需花费过多精力和时间找寻需要的内容…

IDEA 可视化使用 git rebase 合并分支步骤 使git分支树保持整洁

模拟环境 dev 分支开发完一个功能&#xff0c;需要合并到 master 分支&#xff0c;如果现在直接 merge 合并的话 git分支树会出现杂乱分叉&#xff0c;先把 master 分支 rebase 到 dev git分支树就会是整洁的一条直线 git rebase介绍 rebase:翻译成中文是重新设定&#xff0c;…

Linux(网络协议和管理)

后面也会持续更新&#xff0c;学到新东西会在其中补充。 建议按顺序食用&#xff0c;欢迎批评或者交流&#xff01; 缺什么东西欢迎评论&#xff01;我都会及时修改的&#xff01; 在这里真的很感谢这位老师的教学视频让迷茫的我找到了很好的学习视频 王晓春老师的个人空间…

hutool一些典型的方法使用笔记

hutool一些典型的方法使用笔记 1 克隆1.1 深克隆 2类型转换2.1其他类型转换为字符串2.2 转换为日期对象2.3 数组转集合2.4 Unicode和字符串转换2.5 数字转中文 文档地址&#xff1a;https://blog.csdn.net/dxjren/article/details/144468399 1 克隆 1.1 深克隆 定义一个实体类…

一次tomcat实战jvm线上问题定位排查和解决

问题分析&#xff1a; 问题来源是客户通过闲鱼找到了我这边进行问题的排查&#xff0c;给我发了一个报错日志&#xff0c;让我帮忙分析。 首先他的项目比较老&#xff0c;很多年以前开发的软件&#xff0c;但是具体做什么业务我不知道。下面来看日志的报错分析。 问题&#…

go-zero(十二)消息队列

go zero 消息队列 在微服务架构中&#xff0c;消息队列主要通过异步通信实现服务间的解耦&#xff0c;使得各个服务可以独立发展和扩展。 go-zero中使用的队列组件go-queue&#xff0c;是gozero官方实现的基于Kafka和Beanstalkd 的消息队列框架,我们使用kafka作为演示。 一、…