Leetcoder Day16| 二叉树 part05

语言:Java/C++ 

513.找树左下角的值

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

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

示例 1:

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

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
本题需要满足两个条件:(1) 最后一行的(2) 最左边的值
这里需要明白一个概念是,最左边的值未必就是左孩子,右孩子也是可以的。其实这道题求的是: 深度最大的,从左往右数的第一个叶子节点。因此只要先判断左再判断右即可,所以前中后序都可以。

递归法

首先如何判断是否为最后一行:即深度最大的叶子节点所在即最后一行。
如何找最左边:保证优先左边搜索即可。
  1. 确定递归函数的参数和返回值:参数必须有要遍历的树的根节点,额外使用一个变量来记录深度,不需要有返回值。设置一个全局变量result记录结果。
  2. 确定终止条件:当遇到叶子节点时,判断一下是否为最大深度,用叶子节点来更新最大深度。
  3. 确定单层递归逻辑:在找到最大深度时,递归过程依然需要回溯,因为若当前已经没有节点,需要返回到上一个节点继续找另一条路径进行遍历。
class Solution {int maxDepth=-1;int result;void traversal(TreeNode node, int depth){if(node.left==null && node.right==null){ //叶子节点if(depth>maxDepth) {maxDepth=depth;result=node.val;}}if(node.left!=null){depth++;traversal(node.left,depth);depth--;  //回溯}if(node.right!=null){depth++;traversal(node.right,depth);depth--;  //回溯}return;}public int findBottomLeftValue(TreeNode root) {traversal(root,0);return result;}
}

112. 路径总和  

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

示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。
因为本题需要遍历到每一条路径进行判断,所以依然需要回溯。本题没有对中节点的处理,所以前中后序都可以。
  1. 递归函数的参数和返回值:本题需要进行判断是否存在满足条件的路径,所以函数类型为bool,参数有根节点和计数器count。主函数里count传入的是目标值减去根节点的值即target-root.val,因此搜索的过程是一个做减法的过程,如果到某一个叶子节点减去以后刚好count=0,则说明存在满足条件的路径。
  2. 终止条件:如果为叶子节点且count==0,则返回true,否则返回false
  3. 单层递归逻辑:即然前中后都可,用前序遍历,先用count减去当前节点的值,判断如果当前回溯的返回值为true,则继续返回true,回溯再把减去的当前值加回去。
class Solution {boolean traversal(TreeNode node, int count){if(node.left==null && node.right==null && count==0) return true;if(node.left==null && node.right==null && count!=0) return false;//左if(node.left!=null){count-=node.left.val;if(traversal(node.left, count)) return true;  //若之前判断有满足条件的,直接truecount+=node.left.val;}if(node.right!=null){count-=node.right.val;if(traversal(node.right, count)) return true;  //若之前判断有满足条件的,直接truecount+=node.right.val;}return false;}public boolean hasPathSum(TreeNode root, int targetSum) {if(root==null) return false;return traversal(root, targetSum-root.val);}
}

113.路径总和ii

和路径总和1不同的是这里让给出所有符合条件的路径,因此返回值发生了变化,不需要有返回值因为要遍历整个树,设置全局变量记录路径和结果。

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> path =new LinkedList<>();void traversal(TreeNode node, int count){if(node.left==null && node.right == null && count==0){//res.add(path);res.add(new LinkedList<>(path));return;}if(node.left==null && node.right == null && count!=0) return;if(node.left!=null){path.add(node.left.val);count-=node.left.val;traversal(node.left, count);count+=node.left.val;path.removeLast();}if(node.right!=null){path.add(node.right.val);count-=node.right.val;traversal(node.right, count);count+=node.right.val;path.removeLast();}return;}public List<List<Integer>> pathSum(TreeNode root, int targetSum) {res.clear();path.clear();if(root==null) return res;path.add(root.val);traversal(root, targetSum-root.val);return res;}
}
⚠️:在将path添加到res中时,如果单纯的res.add(path),添加的则是同一个 path的引用,而不是新的路径。当修改 path时,之前添加到 res中的路径也会被修改,导致最终结果中出现重复的路径。因此需要在将 path添加到 res中时创建一个新的 path对象,而不是使用现有的 path对象。

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

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如,给出

  • 中序遍历 inorder = [9,3,15,20,7]
  • 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树:
按照理论知识,给出中序和后序遍历的时候,首先需要根据后序遍历找出根节点。随后根据根节点将中序一分为二,然后再根据中序分出来的结果切分后序。重复直到切分完最后一个节点。因此需要反复切割,用到递归。
这其中, 为了高效查找根节点元素在中序遍历数组中的下标,我们选择创建哈希表来存储中序序列,即建立一个(元素,下标)键值对的哈希表。
  1. 递归函数的参数和返回值:不需要有返回值,参数则是后序和中序序列
  2. 终止条件:当前序列为空
  3. 单层递归逻辑:后序数组的最后一个元素,根据这个元素的值找到在中序数组的位置root_idx,将中序数组分为,左中序数组和右中序数组。计算左中序数组的个数,以此来确定后序数组中左后序数组的个数。将后序数组分为左后序和右后序。将后序数组中的最后一个元素去掉。
class Solution {Map<Integer, Integer> map;public TreeNode buildTree(int[] inorder, int[] postorder) {return traversal(inorder, 0, inorder.length, postorder, 0, postorder.length);}public TreeNode traversal(int[] inorder, int inB, int inE, int[] postorder, int postB, int postE){if(inB >= inE || postB >= postE) return null;   //返回空树map = new HashMap<>();for (int i=0; i<inorder.length;i++){map.put(inorder[i], i);    //用map来存放中序数组的值和位置,以实现快速查找}int rootIdx=map.get(postorder[postE-1]);   //在中序数组中查找后序的最后一个元素TreeNode root = new TreeNode(inorder[rootIdx]);int lenofLeft=rootIdx-inB;  //左中数组的个数root.left=traversal(inorder, inB, rootIdx, postorder, postB, postB+lenofLeft);   //保持左闭右开root.right=traversal(inorder, rootIdx+1, inE, postorder, postB+lenofLeft, postE-1);return root;}  
}
105.从前序与中序遍历序列构造二叉树

前序和中序的思路和上面的基本一样,就是把取后序数组的最后一个元素换成取前序数组的第一个元素即可。

class Solution {Map<Integer, Integer> map;public TreeNode traversal(int[] preorder,int preB, int preE, int[] inorder, int inB, int inE){if(preE<=preB||inE<=inB) return null;map=new HashMap<>();for(int i=0; i<inorder.length;i++){map.put(inorder[i], i);}int rootIdx=map.get(preorder[preB]);TreeNode root =new TreeNode(inorder[rootIdx]);int lengthOfLeft=rootIdx-inB;root.left=traversal(preorder, preB+1, lengthOfLeft+preB+1, inorder,inB, rootIdx);root.right=traversal(preorder, lengthOfLeft+preB+1, preE, inorder, rootIdx+1, inE);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {return traversal(preorder, 0, preorder.length, inorder, 0, inorder.length);}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

3个密码学相关的问题

一、离散对数问题&#xff08;Discrete Logarithm Problem, DLP&#xff09; 问题描述&#xff1a;给定 有限阿贝尓群 G中的2个元素a和b&#xff0c;找出最小的正整数x满足&#xff1a;b a ^^ x &#xff08;或者证明这样的x不存在&#xff09;。 二、阶数问题&#xff08;O…

【STM32】硬件SPI读写W25Q64芯片

目录 基础知识回顾&#xff1a; SPI外设简介 SPI框图 主模式全双工连续传输 非连续传输 初始化SPI外设 核心代码 - 交换一个字节 硬件接线图 Code 程序配置过程 MySPI.c MySPI.h W25Q64.c W25Q64.h W25Q64_Ins.h main.c 基础知识回顾&#xff1a; 【STM32】SP…

【压缩感知基础】Nyquist采样定理

Nyquist定理&#xff0c;也被称作Nyquist采样定理&#xff0c;是由哈里奈奎斯特在1928年提出的&#xff0c;它是信号处理领域的一个重要基础定理。它描述了连续信号被离散化为数字信号时&#xff0c;采样的要求以避免失真。 数学表示 Nyquist定理的核心内容可以描述如下&…

命令执行讲解和函数

命令执行漏洞简介 命令执行漏洞产生原因 应用未对用户输入做严格得检查过滤&#xff0c;导致用户输入得参数被当成命令来执行 命令执行漏洞的危害 1.继承Web服务程序的权限去执行系统命会或读写文件 2.反弹shell&#xff0c;获得目标服务器的权限 3.进一步内网渗透 远程代…

自己动手写编译器:使用 PDA 实现增强和属性语法的解析

在前面章节中我们了解了增强语法和属性语法&#xff0c;特别是看到了这两种语法的结合体&#xff0c;本节我们看看如何使用前面我们说过的自顶向下自动机来实现这两种语法结合体的解析&#xff0c;这里使用的方法也是成熟编译器常用的一种语法解析算法。 首先我们先给出上一节…

【运维】站点可靠性工程介绍:研发,运维,SRE,Devops的关系

文章目录 1、什么是SRE2、SRE与研发、运维的区别 1、什么是SRE 站点可靠性工程&#xff08;SRE&#xff09; 是 IT 运维的软件工程方案。 SRE 团队使用软件作为工具&#xff0c;来管理系统、解决问题并实现运维任务自动化。 SRE 执行的任务以前通常由运维团队手动执行&#x…

URL、DNS过滤,AV---防火墙综合实验

拓扑图 该实验之前的配置请看我的上一篇博客&#xff0c;这里仅配置URL、DNS过滤&#xff0c;AV 需求 8&#xff0c;分公司内部的客户端可以通过域名访问到内部的服务器 这次的拓扑图在外网多增加了一个DNS服务器和HTTP服务器 DNS服务器IP&#xff1a;40.0.0.30 HTTP服务器…

计算机视觉主要知识点

计算机视觉是指利用计算机和算法来解析和理解图片和视频中的内容。这是一个跨学科领域&#xff0c;融合了计算机科学、图像处理、机器学习和模式识别等多方面的技术。以下是一些计算机视觉入门的基本知识点&#xff1a; 主要知识点 图像基础&#xff1a; 像素&#xff1a;图片…

文献学习-1-Continuum Robots for Medical Interventions

Chapt 5. 连续体机构分析 5.1 文献学习 5.1.1 Continuum Robots for Medical Interventions Authors: PIERRE E. DUPONT , Fellow IEEE, NABIL SIMAAN , Fellow IEEE, HOWIE CHOSET , Fellow IEEE, AND CALEB RUCKER , Member IEEE 连续体机器人在医学上得到了广泛的应用&a…

深度学习基础之《TensorFlow框架(4)—Operation》

一、常见的OP 1、举例 类型实例标量运算add&#xff0c;sub&#xff0c;mul&#xff0c;div&#xff0c;exp&#xff0c;log&#xff0c;greater&#xff0c;less&#xff0c;equal向量运算concat&#xff0c;slice&#xff0c;splot&#xff0c;canstant&#xff0c;rank&am…

通配符ssl证书产品

SSL数字证书可以对网站传输数据进行加密以及对服务器的身份进行认证。然而&#xff0c;随着互联网的发展&#xff0c;不管是个人还是企事业单位创建的域名网站越来越多&#xff0c;单域名SSL数字证书无法满足需求&#xff0c;因此通配符SSL证书应运而生。今天就随SSL盾小编了解…

【elk查日志 elastic(kibana)】

文章目录 概要具体的使用方式一&#xff1a;查找接口调用历史二&#xff1a;查找自己的打印日志三&#xff1a;查找错误日志 概要 每次查日志&#xff0c;我都需要别人帮我&#xff0c;时间长了总觉得不好意思&#xff0c;所以这次下定决心好好的梳理一下&#xff0c;怎么查日…

文件IO,目录IO的学习

一&#xff0c;头文件的添加 #ifndef _HEAD_H_ //防止重新定义宏 #define _HEAD_H_#include<stdio.h> #include<sys/stat.h> #include<sys/types.h> #include<fcntl.h> #include<unistd.h> #include<string.h>#endif…

SpringBoot + Nacos 实现动态化线程池

1.背景 在后台开发中&#xff0c;会经常用到线程池技术&#xff0c;对于线程池核心参数的配置很大程度上依靠经验。然而&#xff0c;由于系统运行过程中存在的不确定性&#xff0c;我们很难一劳永逸地规划一个合理的线程池参数。 在对线程池配置参数进行调整时&#xff0c;一…

【已解决】PPT无法复制内容怎么办?

想要复制PPT文件里的内容&#xff0c;却发现复制不了&#xff0c;怎么办&#xff1f; 这种情况&#xff0c;一般是PPT文件被设置了以“只读方式”打开&#xff0c;“只读方式”下的PPT无法进行编辑更改&#xff0c;也无法进行复制粘贴的操作。 想要解决这个问题&#xff0c;我…

PHP分析二维数据表(长度|数字字段|空值|纯姓名|英文用户名|科学计数|是否等长|是否唯一)

先看图&#xff0c;后有完整代码 <?php $t "Excel数据转Sql查询系统字段半智能分析"; $s "Excel复制过来的二维结构表内容,分析查询条件&#xff01;"; $x "字段|最大长度|长度有|数字字段|空值存在|纯姓名|英文用户名|科学计数|是否等长|是否…

DP读书:《openEuler操作系统》(十)套接字 Socket 数据传输的基本模型

10min速通Socket 套接字简介数据传输基本模型1.TCP/IP模型2.UDP模型 套接字类型套接字&#xff08;Socket&#xff09;编程Socket 的连接1.连接概述(1)基本概念(2)连接状态(3)连接队列 2.建立连接3.关闭连接 socket 编程接口介绍数据的传输1. 阻塞与非阻塞2. I/O复用 数据的传输…

2024.02.20作业

1. 使用多进程完成两个文件的拷贝&#xff0c;父进程拷贝前一半&#xff0c;子进程拷贝后一半&#xff0c;父进程回收子进程的资源 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #includ…

C#,二叉搜索树(Binary Search Tree)的迭代方法与源代码

1 二叉搜索树 二叉搜索树&#xff08;BST&#xff0c;Binary Search Tree&#xff09;又称二叉查找树或二叉排序树。 一棵二叉搜索树是以二叉树来组织的&#xff0c;可以使用一个链表数据结构来表示&#xff0c;其中每一个结点就是一个对象。 一般地&#xff0c;除了key和位置…

【AIGC】Stable Diffusion的常见错误

Stable Diffusion 在使用过程中可能会遇到各种各样的错误。以下是一些常见的错误以及可能的解决方案&#xff1a; 模型加载错误&#xff1a;可能出现模型文件损坏或缺失的情况。解决方案包括重新下载模型文件&#xff0c;确保文件完整并放置在正确的位置。 依赖项错误&#x…