Leetcode二叉树部分笔记

ops/2024/12/16 22:48:03/

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

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/ops/142484.html

相关文章

JS中的Promise用法大全

目录 一、相关概念介绍1.什么是Promise2.Promise状态3.创建Promise4.then()方法5.catch方法6.链式调用7.异步编程 二、使用1.构造Promise2.executor 函数3.then() 方法4.then() 方法返回的Promise的状态 三、Async/Await语法糖四、Promise应用场景五、总结 一、相关概念介绍 1…

蓝桥杯刷题——day1

蓝桥杯刷题——day1 题目一题干题目解析代码 题目二题干题目解析代码 题目一 题干 给定一个字符串 s &#xff0c;验证 s 是否是 回文串 &#xff0c;只考虑字母和数字字符&#xff0c;可以忽略字母的大小写。本题中&#xff0c;将空字符串定义为有效的 回文串 。 题目链接&a…

【FFmpeg】FFmpeg 内存结构 ⑥ ( 搭建开发环境 | AVPacket 创建与释放代码分析 | AVPacket 内存使用注意事项 )

文章目录 一、搭建开发环境1、开发环境搭建参考2、项目搭建 二、AVPacket 创建与释放代码分析1、AVPacket 创建与释放代码2、Qt 单步调试方法3、单步调试 - 分析 AVPacket 创建与销毁代码 三、AVPacket 内存使用注意事项1、谨慎使用 av_init_packet 函数2、av_init_packet 函数…

Elasticsearch Java Api Client中DSL语句的查询方法汇总

说明&#xff1a;示例代码依赖的是co.elastic.clients:elasticsearch-java:8.16.1。 1、termQuery 方法 用途&#xff1a;用于精确匹配某个字段的完全相等的值。这在查询如文档的 ID、状态码等具有明确取值的字段时非常有用。参数说明&#xff1a; field&#xff1a;这是一个…

游戏引擎学习第45天

仓库: https://gitee.com/mrxiao_com/2d_game 回顾 我们刚刚开始研究运动方程&#xff0c;展示了如何处理当人物遇到障碍物时的情况。有一种版本是角色会从障碍物上反弹&#xff0c;而另一版本是角色会完全停下来。这种方式感觉不太自然&#xff0c;因为在游戏中&#xff0c;…

新能源汽车安全充电管理方案

摘要:近年来&#xff0c;随着国家碳达峰和碳中和目标的提出&#xff0c;国家节能减排政策实施力度的进一步加大大众的环保意识、环保理念进一步深入人心&#xff0c;同时根据国家战略安全需要&#xff0c;新能源汽车行业异军突起&#xff0c;发展迅猛。随着新能源汽车数量的不断…

Mac/Windows端长期破解myBase8方法(无需安装火绒)

提醒 不管哪个端&#xff0c;都需要先退出myBase。 Mac 进入用户根目录/Users/c0ny100&#xff0c;即下边是Macintosh HD > 用户 > [你的用户名]这个界面然后按ShiftCommond.&#xff0c;显示隐藏文件。找到.Mybase8.ini文件 打开.Mybase8.ini文件&#xff0c;删除Fir…

Unity 将数字1234转换为字母ABCD

需求如下&#xff1a; 数字1&#xff0c;转换后为&#xff1a;A 数字2&#xff0c;转换后为&#xff1a;B 数字3&#xff0c;转换后为&#xff1a;C 数字4&#xff0c;转换后为&#xff1a;D 数字123&#xff0c;转换后为&#xff1a;ABC C#实现代码如下&#xff1a; pri…