代码随想录算法训练营第十七天| 513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

本文主要是介绍代码随想录算法训练营第十七天| 513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

513.找树左下角的值

public int findBottomLeftValue(TreeNode root) {List<Integer> path = new ArrayList<>();List<List<Integer>> ans = new ArrayList<>();Boolean[] flag = new Boolean[1];flag[0] = true;dfs(root, path, ans, flag);int maxSizeIndex = 0;if (ans.size() == 0) {return -1;}int maxSize = ans.get(0).size();for (int i = 0; i < ans.size(); i++) {if (maxSize < ans.get(i).size()) {maxSize = ans.get(i).size();maxSizeIndex = i;}}if (ans.get(maxSizeIndex).size() == 0) {return -1;}return ans.get(maxSizeIndex).get(ans.get(maxSizeIndex).size() - 1);
}public void dfs(TreeNode root, List<Integer> path, List<List<Integer>> ans, Boolean[] flag) {if (root == null) {return;}path.add(root.val);if (root.left == null && root.right == null) {ans.add(new ArrayList<Integer>(path));}// flag[0] = true;dfs(root.left, path, ans, flag);// flag[0] = false;dfs(root.right, path, ans, flag);path.remove(path.size() - 1);}

112. 路径总和

public boolean hasPathSum(TreeNode root, int targetSum) {List<Integer> path = new ArrayList<>();List<List<Integer>> ans = new ArrayList<>();dfs(root, path, ans);for (List<Integer> an : ans) {int sum = 0;for (Integer integer : an) {sum += integer;}if (sum == targetSum) {return true;}}return false;
}public void dfs(TreeNode root, List<Integer> path, List<List<Integer>> ans) {if (root == null) {return;}path.add(root.val);if (root.left == null && root.right == null) {ans.add(new ArrayList<Integer>(path));}dfs(root.left, path, ans);dfs(root.right, path, ans);path.remove(path.size() - 1);}

105.从前序与中序遍历序列构造二叉树

public TreeNode buildTree(int[] preorder, int[] inorder) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < inorder.length; i++) {map.put(inorder[i], i);}return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1, map);
}public TreeNode build(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd, Map<Integer, Integer> inMap) {if (preStart > preEnd || inStart > inEnd) {return null;}int rootVal = preorder[preStart];TreeNode root = new TreeNode(rootVal);Integer rootIndex = inMap.get(rootVal);//左子树的长度int instance = rootIndex - inStart;//左递归,分解成子问题,每次递归去除根节点,保留左子树的节点  root.left = build(preorder, inorder, preStart + 1, preStart + instance, inStart, inStart + instance - 1, inMap);//右递归,分解成子问题,每次递归去除根节点,保留右子树的节点  root.right = build(preorder, inorder, preStart + instance + 1, preEnd, inStart + instance + 1, inEnd, inMap);return root;
}

这篇关于代码随想录算法训练营第十七天| 513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/603050

相关文章

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

使用Dify访问mysql数据库详细代码示例

《使用Dify访问mysql数据库详细代码示例》:本文主要介绍使用Dify访问mysql数据库的相关资料,并详细讲解了如何在本地搭建数据库访问服务,使用ngrok暴露到公网,并创建知识库、数据库访... 1、在本地搭建数据库访问的服务,并使用ngrok暴露到公网。#sql_tools.pyfrom

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Java springBoot初步使用websocket的代码示例

《JavaspringBoot初步使用websocket的代码示例》:本文主要介绍JavaspringBoot初步使用websocket的相关资料,WebSocket是一种实现实时双向通信的协... 目录一、什么是websocket二、依赖坐标地址1.springBoot父级依赖2.springBoot依赖

讯飞webapi语音识别接口调用示例代码(python)

《讯飞webapi语音识别接口调用示例代码(python)》:本文主要介绍如何使用Python3调用讯飞WebAPI语音识别接口,重点解决了在处理语音识别结果时判断是否为最后一帧的问题,通过运行代... 目录前言一、环境二、引入库三、代码实例四、运行结果五、总结前言基于python3 讯飞webAPI语音

什么是 Java 的 CyclicBarrier(代码示例)

《什么是Java的CyclicBarrier(代码示例)》CyclicBarrier是多线程协同的利器,适合需要多次同步的场景,本文通过代码示例讲解什么是Java的CyclicBarrier,感... 你的回答(口语化,面试场景)面试官:什么是 Java 的 CyclicBarrier?你:好的,我来举个例

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...