Java算法练习4

Java算法练习4

    • 1.1 [145. 二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/)
    • 1.2 [173. 二叉搜索树迭代器](https://leetcode.cn/problems/binary-search-tree-iterator/)
    • 1.3 [98. 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/)
    • 1.4 [102. 二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/)
    • 1.5 [429. N 叉树的层序遍历](https://leetcode.cn/problems/n-ary-tree-level-order-traversal/)
    • 1.6 [513. 找树左下角的值](https://leetcode.cn/problems/find-bottom-left-tree-value/)
    • 1.7 [404. 左叶子之和](https://leetcode.cn/problems/sum-of-left-leaves/)

1.1 145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历

示例 1:

img

输入:root = [1,null,2,3]
输出:[3,2,1]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List list = new ArrayList<Integer>();lrp(root,list);return list;}public void lrp(TreeNode root,List<Integer> list){if(root == null) return;lrp(root.left,list);lrp(root.right,list);list.add(root.val);}
}

1.2 173. 二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器:

  • BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于 BST 中的任何元素。
  • boolean hasNext() 如果向指针右侧遍历存在数字,则返回 true ;否则返回 false
  • int next()将指针向右移动,然后返回指针处的数字。

注意,指针初始化为一个不存在于 BST 中的数字,所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的,也就是说,当调用 next() 时,BST 的中序遍历中至少存在一个下一个数字。

示例:

img

输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class BSTIterator {private int index;private List<Integer> list;public BSTIterator(TreeNode root) {list = new ArrayList<Integer>();index = 0;lpr(root,list);}public int next() {return list.get(index++);}public boolean hasNext() {return index<list.size();}public void lpr(TreeNode root,List<Integer> list){if(root == null) return;lpr(root.left,list);list.add(root.val);lpr(root.right,list);}
}/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator obj = new BSTIterator(root);* int param_1 = obj.next();* boolean param_2 = obj.hasNext();*/

1.3 98. 验证二叉搜索树

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

img

输入:root = [2,1,3]
输出:true

示例 2:

img

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private List<Integer> list;public boolean isValidBST(TreeNode root) {list = new ArrayList<Integer>();lpr(root,list);for (int i = 1; i < list.size(); i++) {if(list.get(i) <= list.get(i-1)) return false;}return true;}public void lpr(TreeNode root,List<Integer> list){if(root == null) return;lpr(root.left,list);list.add(root.val);lpr(root.right,list);}}

1.4 102. 二叉树的层序遍历

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

示例 1:

img

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list = new ArrayList<>();Queue<TreeNode> q = new LinkedList<>();q.offer(root);while(q.isEmpty() == false){ //判断队列是否为空,为空则证明遍历结束int size = q.size();List<Integer> level = new LinkedList();for(int i = 0;i < size; i++){TreeNode cur = q.poll(); //将节点出队列if(cur == null) continue; level.add(cur.val); q.offer(cur.left); //将左子节点放入队列q.offer(cur.right); //将右子节点放入队列}if(level.isEmpty() == false){ list.add(level);}}return list;}
}

1.5 429. N 叉树的层序遍历

给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。

树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。

示例 1:

img

输入:root = [1,null,3,2,4,null,5,6]
输出:[[1],[3,2,4],[5,6]]

示例 2:

img

输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> list = new ArrayList();Queue<Node> q = new LinkedList();q.offer(root);while(!q.isEmpty()){int size = q.size();List<Integer> level = new ArrayList();for(int i = 0;i < size; i++){Node cur = q.poll();if(cur == null) continue;level.add(cur.val);List<Node> l = cur.children; for(Node child : l){q.offer(child);}}if(!level.isEmpty()) list.add(level);}return list;}
}

1.6 513. 找树左下角的值

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

img

输入: root = [2,1,3]
输出: 1

示例 2:

img

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int findBottomLeftValue(TreeNode root) {int ret = 0;Queue<TreeNode> q = new LinkedList();q.offer(root);while(!q.isEmpty()){// int size = q.size();// for(int i = 0;i <size;i++){TreeNode cur = q.poll();if(cur == null) continue;q.offer(cur.right);q.offer(cur.left);ret = cur.val;// }}return ret;}
}

1.7 404. 左叶子之和

给定二叉树的根节点 root ,返回所有左叶子之和。

示例 1:

img

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

示例 2:

输入: root = [1]
输出: 0
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int sum = 0;public int sumOfLeftLeaves(TreeNode root) {if(root == null) return 0;if(root.left != null && root.left.left == null && root.left.right == null) sum += root.left.val;sumOfLeftLeaves(root.left);sumOfLeftLeaves(root.right);return sum;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2774528.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【Java数据结构】ArrayList和LinkedList的遍历

一&#xff1a;ArrayList的遍历 import java.util.ArrayList; import java.util.Iterator; import java.util.List;/*** ArrayList的遍历*/ public class Test {public static void main(String[] args) {List<Integer> list new ArrayList<>();list.add(5);list…

MySQL篇之定位与优化MySQL慢查询

一、如何定位慢查询 1.方案一&#xff1a;开源工具 调试工具&#xff1a;Arthas。 运维工具&#xff1a;Prometheus 、Skywalking。 2.方案二&#xff1a;MySQL自带慢日志 慢查询日志记录了所有执行时间超过指定参数&#xff08;long_query_time&#xff0c;单位&#xff1a;…

Filter 实现过滤符合条件的请求并落库

其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一、配置过滤器类 二、定义数据表、实体类、Mapper 2.1 DDL 2.2 实体类 2.3 Mapper 三、创建一个过滤器 四、实现 Nacos 配置…

分享86个行业PPT,总有一款适合您

分享86个行业PPT&#xff0c;总有一款适合您 86个行业PPT下载链接&#xff1a;https://pan.baidu.com/s/1avbzwqK8ILLWYIOylK1aRQ?pwd8888 提取码&#xff1a;8888 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 学习知识费力气&#xff0c;收集整理更不易…

住宅供暖设备行业调研:市场环境将稳定发展阶段中

为使人们生活或进行生产的空间保持在适宜的热状态而设置的供热设施。 向一定的空间加热量的办法&#xff0c;可以直接把产生热量的火炉装在其中;也可以抽出其中的空气&#xff0c;加热后再送回;也可以在其中装置保持在较高温度的物体&#xff0c;向所在空间放热。这种温度较高的…

Elasticsearch:通过 ingest pipeline 对大型文档进行分块

在我之前的文章 “Elasticsearch&#xff1a;使用 LangChain 文档拆分器进行文档分块” 中&#xff0c;我详述了如何通过 LangChain 对大的文档进行分块。那个分块的动作是通过 LangChain 在 Python 中进行实现的。对于使用版权的开发者来说&#xff0c;我们实际上是可以通过 i…

【c++】模板---函数模板

1.泛型编程 如何实现一个通用的交换函数呢&#xff1f; void Swap(int& left, int& right) {int temp left;left right;right temp; } void Swap(double& left, double& right) {double temp left;left right;right temp; } void Swap(char& left,…

嵌入式学习之Linux入门篇笔记——18,makefile基本语法(下)

配套视频学习链接&#xff1a;http://【【北京迅为】嵌入式学习之Linux入门篇】 https://www.bilibili.com/video/BV1M7411m7wT/?p4&share_sourcecopy_web&vd_sourcea0ef2c4953d33a9260910aaea45eaec8 1.wildcard 函数 格式&#xff1a;$&#xff08;wildcard PAT…

爬虫系列-第一个爬虫

&#x1f308;个人主页: 会编程的果子君 ​&#x1f4ab;个人格言:“成为自己未来的主人~” 首先&#xff0c;我们需要回顾一下爬虫的概念&#xff0c;爬虫就是我们通过我们写的程序去抓取互联网上的数据资源&#xff0c;比如&#xff0c;此时我需要百度的资源&#xff0c;在不…

spring Bean生命周期 源代码分析 AbstractAutowireCapableBeanFactory createBean doCreateBean

文章目录 一、生命周期关键步骤1.1 前置条件1.2 创建bean 二、Bean生命周期、核心源码分析2.1 前置条件, 源代码2.2 创建bean, 源代码 一、生命周期关键步骤 1.1 前置条件 1.创建rootBean 生成RootBeanDefinition 2.对bean定义的方法&#xff0c;进行验证、重写 调用方法pre…

Blender教程(基础)-顶点挤出扩展-19

shiftA新建一个平面 编辑模式下&#xff0c;选中三个点&#xff0c;按X弹出按顶点删除 删除完成只剩下一个顶点 选中顶点按字母E在X轴挤出&#xff0c;按字母E在Y轴挤出 选中三个顶点按字母E延Z轴挤出 新建平面&#xff0c;按数字7到顶视图 选中顶点按E延X轴挤出 …

通用的网站炫酷底部美化代码分享

网站炫酷底部美化代码介绍 这段代码采用了最新的前端技术&#xff0c;确保在各种浏览器和设备上都能完美展现。它包含响应式设计元素&#xff0c;这意味着无论用户是通过电脑、平板还是手机访问您的网站&#xff0c;底部都能呈现出最佳的效果。 此外&#xff0c;我们还特别注…

单片机——ISP下载、ICP下载、IAP下载

文章目录 ISPICPIAP ISP 在线系统编程&#xff0c;使用引导程序加上外围UART/SPI接口烧录 其本质是将程序的hex文件烧录到板子里的过程 可以使用flymcu这个软件 System memory是STM32在出厂时&#xff0c;由ST在这个区域内部预置了一段BootLoader&#xff0c; 也就是我们常说…

机器人运动学林沛群——变换矩阵

对于仅有移动&#xff0c;由上图可知&#xff1a; A P B P A P B o r g ^AP^BP^AP_{B org} APBPAPBorg​ 对于仅有转动&#xff0c;可得&#xff1a; A P B A R B P ^AP^A_BR^BP APBA​RBP 将转动与移动混合后&#xff0c;可得&#xff1a; 一个例子 在向量中&#xff…

猫头虎分享已解决Bug || TypeError: this.$store.commit is not a function in Vue

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

c语言中的模拟多态性

在C语言中模拟多态性 多态性是面向对象编程中的一个核心概念&#xff0c;它允许我们通过一个共同的接口来操作不同的数据类型。虽然C语言是一种过程式语言&#xff0c;本身不直接支持面向对象的特性&#xff0c;如继承、封装和多态&#xff0c;但我们可以通过一些技巧来模拟这些…

@RequestBody、@RequestParam、@RequestPart使用方式和使用场景

RequestBody和RequestParam和RequestPart使用方式和使用场景 1.RequestBody2.RequestParam3.RequestPart 1.RequestBody 使用此注解接收参数时&#xff0c;适用于请求体格式为 application/json&#xff0c;只能用对象接收 2.RequestParam 接收的参数是来自HTTP 请求体 或 请…

关于 Ant Design 的 Upload 组件使用 action 自动上传出现跨域问题的解决

问题描述 使用 Ant Design 的 Upload 组件时&#xff0c;可以通过 action 属性指定上传地址实现选择文件自动上传。但在我选择文件上传后浏览器控制台一直出现跨域错误。关键我已经在后端处理了跨域&#xff0c;还是一直会出现跨域错误。而且其它请求都可以正常处理跨域&#…

微软.NET6开发的C#特性——接口和属性

我是荔园微风&#xff0c;作为一名在IT界整整25年的老兵&#xff0c;看到不少初学者在学习编程语言的过程中如此的痛苦&#xff0c;我决定做点什么&#xff0c;下面我就重点讲讲微软.NET6开发人员需要知道的C#特性。 C#经历了多年发展&#xff0c; 进行了多次重大创新&#xf…

如何利用IP定位技术锁定网络攻击者

在当今高度互联的数字世界中&#xff0c;网络安全威胁日益猖獗。为了维护网络空间的安全与稳定&#xff0c;追踪并锁定网络攻击者成为了关键一环。而IP定位技术&#xff0c;作为一种重要的追踪手段&#xff0c;正发挥着越来越重要的作用。 IP定位技术&#xff0c;简而言之&…