day16--513.找树左下角的值+112. 路径总和+106.从中序与后序遍历序列构造二叉树

本文主要是介绍day16--513.找树左下角的值+112. 路径总和+106.从中序与后序遍历序列构造二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、513.找树左下角的值

题目链接:https://leetcode.cn/problems/find-bottom-left-tree-value/
文章讲解:https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html
视频讲解:https://www.bilibili.com/video/BV1fA4y1o715

1.1 初见思路

  1. 层序遍历,最后一行的第一个元素就是要找的值
  2. 怎么知道到了最后一层:每层都更新一遍最左的元素值,没有再有下一层的时候就说明到最后一层了

1.2 具体实现

class Solution {int leftVal=0;public int findBottomLeftValue(TreeNode root) {Deque<TreeNode> queue = new LinkedList<>();queue.offer(root);int res = 0;while(!queue.isEmpty()){int size = queue.size();for(int i=0;i<size;i++){TreeNode node = queue.poll();if(i==0){res=node.val;}if(node.left!=null){queue.offer(node.left);}if(node.right!=null){queue.offer(node.right);}}}return res;}}

1.3 重难点

二、112. 路径总和

题目链接:https://leetcode.cn/problems/path-sum/
文章讲解:https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
视频讲解:https://www.bilibili.com/video/BV19t4y1L7CR

2.1 初见思路

  1. 递归+回溯
  2. 剪枝,当算出总和已经大于target了,这条分支的剩余计算都不用做了

2.2 具体实现

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) {return false;}return hasSum(root, targetSum);}public boolean hasSum(TreeNode node, int target) {target -= node.val;if (node.left == null && node.right == null) {if (target == 0) {return true;}return false;}if (node.left != null) {boolean leftFlag = hasSum(node.left, target);if (leftFlag) {return true;}}if (node.right != null) {boolean rightFlag = hasSum(node.right, target);if (rightFlag) {return true;}}return false;}
}

2.3 重难点

三、 106.从中序与后序遍历序列构造二叉树

题目链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
文章讲解:https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解:https://www.bilibili.com/video/BV1vW4y1i7dn

3.1 初见思路

  1. 中序:左中右,后续:左右中
  2. 先用后序遍历找到根节点,再去中序中进行分割

3.2 具体实现

class Solution {HashMap<Integer,Integer> inorderArrayMap = new HashMap<>();int[] post;public TreeNode buildTree(int[] inorder, int[] postorder) {for(int i = 0;i < inorder.length; i++) {inorderArrayMap.put(inorder[i], i);//妙啊!将节点值及索引全部记录在哈希表中}post = postorder;TreeNode root = buildTree(0, inorder.length - 1, 0, post.length - 1);return root;}public TreeNode buildTree(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd) {if(inorderEnd < inorderStart || postorderEnd < postorderStart) return null;int root = post[postorderEnd];//根据后序遍历结果,取得根节点int rootIndexInInorderArray = inorderArrayMap.get(root);//获取对应的索引TreeNode node = new TreeNode(root);//创建该节点node.left = buildTree(inorderStart, rootIndexInInorderArray - 1, postorderStart, postorderStart + rootIndexInInorderArray - inorderStart - 1);node.right = buildTree(rootIndexInInorderArray + 1, inorderEnd, postorderStart + rootIndexInInorderArray - inorderStart, postorderEnd - 1);return node;//注意!返回的是新建的node!}
}

3.3 重难点

  • 思路不难,实现有难度
  • 把中序遍历的值和下标存储在map中;这样能在后序遍历找到中节点后快速找到对应的在中序遍历中的下标

在这里插入图片描述

这篇关于day16--513.找树左下角的值+112. 路径总和+106.从中序与后序遍历序列构造二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价

python进行while遍历的常见错误解析

《python进行while遍历的常见错误解析》在Python中选择合适的遍历方式需要综合考虑可读性、性能和具体需求,本文就来和大家讲解一下python中while遍历常见错误以及所有遍历方法的优缺点... 目录一、超出数组范围问题分析错误复现解决方法关键区别二、continue使用问题分析正确写法关键点三

一文详解如何查看本地MySQL的安装路径

《一文详解如何查看本地MySQL的安装路径》本地安装MySQL对于初学者或者开发人员来说是一项基础技能,但在安装过程中可能会遇到各种问题,:本文主要介绍如何查看本地MySQL安装路径的相关资料,需... 目录1. 如何查看本地mysql的安装路径1.1. 方法1:通过查询本地服务1.2. 方法2:通过MyS

PostgreSQL 序列(Sequence) 与 Oracle 序列对比差异分析

《PostgreSQL序列(Sequence)与Oracle序列对比差异分析》PostgreSQL和Oracle都提供了序列(Sequence)功能,但在实现细节和使用方式上存在一些重要差异,... 目录PostgreSQL 序列(Sequence) 与 oracle 序列对比一 基本语法对比1.1 创建序

Java遍历HashMap的6种常见方式

《Java遍历HashMap的6种常见方式》这篇文章主要给大家介绍了关于Java遍历HashMap的6种常见方式,方法包括使用keySet()、entrySet()、forEach()、迭代器以及分别... 目录1,使用 keySet() 遍历键,再通过键获取值2,使用 entrySet() 遍历键值对3,