平衡二叉树,二叉树的路径,左叶子之和

news/2024/4/15 4:21:49/文章来源:https://blog.csdn.net/2302_77168608/article/details/136427722

第六章   二叉树part04

今日内容: 

  1.  110.平衡二叉树 
  1.  257. 二叉树的所有路径 
  1.  404.左叶子之和 

 110.平衡二叉树 (优先掌握递归)

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false

递归法:

递归三步曲分析:

  1. 明确递归函数的参数和返回值

参数:当前传入节点。 返回值:以当前传入节点为根节点的树的高度。那么如何标记左右子树是否差值大于1呢?

如果当前传入节点为根节点的二叉树已经不是二叉平衡树了,还返回高度的话就没有意义了。

所以如果已经不是二叉平衡树了,可以返回-1 来标记已经不符合平衡树的规则了。

  1. 明确终止条件

递归的过程中依然是遇到空节点了为终止,返回0,表示当前节点为根节点的树高度为0

  1. 明确单层递归的逻辑

如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢?当然是其左子树高度和其右子树高度的差值。

分别求出其左右子树的高度,然后如果差值小于等于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 boolean isBalanced(TreeNode root) {

        return getHeight(root)!=-1;

    }

    public int getHeight(TreeNode root)

    {

        if(root==null) return 0;

        int leftHeight = getHeight(root.left);

        if(leftHeight==-1)return -1;

        int rightHeight = getHeight(root.right);

        if(rightHeight==-1)return -1;

        if(Math.abs(leftHeight-rightHeight)>1) return -1;

        else return Math.max(leftHeight,rightHeight)+1;

    }

}

257. 二叉树的所有路径 

给定一个二叉树,返回所有从根节点到叶子节点的路径

思路

这道题目要求从根节点到叶子的路径,所以需要前序遍历,这样才方便让父节点指向孩子节点,找到对应的路径。

在这道题目中将第一次涉及到回溯,因为我们要把路径记录下来,需要回溯来回退一个路径再进入另一个路径。

递归

  1. 递归函数参数以及返回值

要传入根节点,记录每一条路径的path,和存放结果集的result,这里递归不需要返回值。

  1. 确定递归终止条件

本题要找到叶子节点,就开始结束的处理逻辑了(把路径放进result里)。

那么什么时候算是找到了叶子节点? 是当 cur不为空,其左右孩子都为空的时候,就找到叶子节点。

  1. 确定单层递归逻辑

因为是前序遍历,需要先处理中间节点,中间节点就是我们要记录路径上的节点,先放进path中。

然后是递归和回溯的过程,上面说过没有判断cur是否为空,那么在这里递归的时候,如果为空就不进行下一层递归了。

回溯和递归是一一对应的,有一个递归,就要有一个回溯。

/**

 * 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<String> binaryTreePaths(TreeNode root) {

        List<String> result = new ArrayList<>();

        List<Integer> paths = new ArrayList<>();

        if(root==null) return result;

        travesal(root,result,paths);

        return result;

    }

    public void travesal(TreeNode root,List<String> result,List<Integer> paths)

    {

        paths.add(root.val);

        if(root.left==null&&root.right==null)

        {

            StringBuilder sb = new StringBuilder();

            for(int i=0;i<paths.size()-1;i++)  sb.append(paths.get(i)).append("->");

            sb.append(paths.get(paths.size()-1));

            String path = sb.toString();

            result.add(path);

            return;

        }

        if(root.left!=null)

        {

            travesal(root.left,result,paths);

            paths.remove(paths.size()-1);

        }

        if(root.right!=null)

        {

            travesal(root.right,result,paths);

            paths.remove(paths.size()-1);

        }

    }

}

404.左叶子之和 (优先掌握递归)

计算给定二叉树的所有左叶子之和。

首先要注意是判断左叶子,不是二叉树左侧节点,所以不要上来想着层序遍历。

节点A的左孩子不为空,且左孩子的左右孩子都为空(说明是叶子节点),那么A节点的左孩子为左叶子节点

判断当前节点是不是左叶子是无法判断的,必须要通过节点的父节点来判断其左孩子是不是左叶子。

递归法

递归的遍历顺序为后序遍历(左右中),是因为要通过递归函数的返回值来累加求取左叶子数值之和。

递归三部曲:

  1. 确定递归函数的参数和返回值

判断一个树的左叶子节点之和,那么一定要传入树的根节点,递归函数的返回值为数值之和,所以为int使用题目中给出的函数就可以了。

  1. 确定终止条件

如果遍历到空节点,那么左叶子值一定是0

只有当前遍历的节点是父节点,才能判断其子节点是不是左叶子。 所以如果当前遍历的节点是叶子节点,那其左叶子也必定是0

  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 int sumOfLeftLeaves(TreeNode root) {

        if(root==null) return 0;

        if(root.left==null&&root.right==null) return 0;

        int leftSum = sumOfLeftLeaves(root.left);

        if(root.left!=null&&root.left.left==null&&root.left.right==null)

        leftSum = root.left.val;

        int rightSum = sumOfLeftLeaves(root.right);

        int sum = leftSum+rightSum;

        return sum;

    }

}

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

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

相关文章

Java面试篇【并发编程】常见面试题(2024最新)

Java并发编程常见面试题 1.什么是线程和进程&#xff1f; 进程是操作系统分配资源的最小单位&#xff0c;各个进程之间占据独立的寻址空间&#xff0c;运行也是独立运行&#xff0c;进程间通信需要一些机制。进程间切换需要的开销较大。 线程是程序执行的基本单位&#xff0c…

Docker知识点总结二

四、 Docker 架构 Docker使用客户端-服务器(C/S)架构模式&#xff0c;使用远程API来管理和创建Docker容器。 介绍&#xff1a; 1、Docker的客户端client&#xff0c;我们在命令行发送一些信息(命令)给Docker服务端。2、中间这个就是Docker的服务端&#xff0c;在这个服务端里面…

网络安全是什么

网络安全是一种保护计算机、服务器、移动设备、电子系统、网络和数据免受恶意攻击的技术&#xff0c;这种技术也称为信息技术安全或电子信息安全。该术语适用于从业务到移动计算的各种环境&#xff0c;可以分为几个常见类别: 网络安全是一种保护计算机网络免受入侵者&#xff0…

【MySQL篇】 MySQL基础学习

前言 在做项目的过程中&#xff0c;深深感悟到一个扎实的MySQL基础是多么重要&#xff0c;这篇文章就用来记录一下我对于MySQL的复习&#xff0c;下面开始介绍了。 MySQL 是一款开源免费的数据库。后端程序员的工作离不开与数据库打交道&#xff0c;MySQL因其简单易懂、使用方…

一次直播和图像识别技术应用的探索之旅

背景 Think Better 很多行业都在“卷”&#xff0c;作为金融科技行业的信也&#xff0c;也不例外。除了卷云计算、大数据和人工智能这些非常有深度的技术以外&#xff0c;信也向着技术融合创新的方向逐步探索&#xff0c;做得更好一些&#xff0c;为用户提供更好的价值&#xf…

NodeJS实现插入排序算法

NodeJS实现插入排序算法 以下是使用Node.js实现插入排序算法的示例代码&#xff1a; function insertionSort(arr) {const n arr.length;for (let i 1; i < n; i) {let key arr[i];let j i - 1;// 将比key大的元素向右移动一位while (j > 0 && arr[j] >…

如何一键批量采集拼多多商品图片?无压缩高清主图/sku图/详情和视频下载|拼多多商品数据采集接口

大家好&#xff0c;这期我教下大家怎么下载拼多多上面的商品主图、详情页图、SKU图、主图视频、详情页视频的下载教程~~ 运营一个多多电商店铺&#xff0c;上架商品&#xff0c;我们都需要采集大量的商品图片进行分析和参考&#xff0c;一张张下载的话将耗费大量时间和精力&am…

(3)(3.3) MAVLink高延迟协议

文章目录 前言 1 配置 2 说明 3 消息说明 前言 ArduPilot 支持 MAVLink 高延迟协议(MAVLink High Latency)。该协议专为卫星或 LoRA 等低带宽或高成本链路而设计。 在此协议中&#xff0c;每 5s 只发送一次 HIGH_LATENCY2 MAVLink 信息。对 MAVLink 命令或请求&#xff08…

word转PDF的方法 简介快速

在现代办公环境中&#xff0c;文档格式转换已成为一项常见且重要的任务。其中&#xff0c;将Word文档转换为PDF格式的需求尤为突出&#xff0c;将Word文档转换为PDF格式具有多方面的优势和应用场景。无论是为了提高文档的可读性和稳定性、保障文档的安全性和保护机制、还是为了…

【STM32详解FLASH闪存编程原理与步骤】

STM32详解FLASH闪存编程原理与步骤 FLASH编程注意事项FLASH编程过程STM32的FLASH擦除过程FLASH全片擦除FLASH操作总结锁定解锁函数写操作函数擦除函数获取状态函数等待操作完成函数读FLASH特定地址数据函数 FLASH编程注意事项 1.STM32复位后&#xff0c;FPEC模块是被保护的&am…

力扣经典题目解析--滑动窗口最大值

原题地址: . - 力扣&#xff08;LeetCode&#xff09; 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1&#xff1a;…

【docker基础学习之】镜像相关

下面是在工作过遇到的一些实际例子&#xff0c;谨以此作为笔记参考 目录 1.背景2. 寻找方案3. 如何解决4.解决步骤4.1 DockerFile4.2 现在要做的 1.背景 部署&#xff08;迁移&#xff09;项目时发现&#xff0c;项目的excel导出功能报错&#xff0c;错误如下&#xff1a; 问…

[C语言]——分支和循环(2)

目录 一.逻辑操作符&#xff1a;&& , || , &#xff01; 1.逻辑取反运算符! 2.与运算符&& 3.或运算符 4.练习&#xff1a;闰年的判断 5.短路 二.switch语句 1.if语句和switch语句的对比 2.switch语句中的break 3.switch语句中的default 4.switch…

微服务day03-Nacos配置管理与Nacos集群搭建

一.Nacos配置管理 Nacos不仅可以作为注册中心&#xff0c;可以进行配置管理 1.1 统一配置管理 统一配置管理可以实现配置的热更新&#xff08;即不用重启当服务发生变更时也可以直接更新&#xff09; dataId格式&#xff1a;服务名-环境名.yaml&#xff0c;分组一般使用默认…

【vue】ant-design弹出框无法关闭和runtimecore提示isFucntion is not function的问题修复

【vue】ant-design弹出框无法关闭和runtimecore提示isFucntion is not function的问题修复&#xff0c;初步分析是vue发布3.4版本以后引起的兼容性问题。 问题截图&#xff1a; 1.isFucntion is not function&#xff0c;是由于vue升级后众多插件版本不匹配造成的问题 2.弹框…

18.网络游戏逆向分析与漏洞攻防-网络通信数据包分析工具-数据分析工具数据与消息配置的实现

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 上一个内容&#xff1a;17.数据分析工具配置功能的实现 码云地址&#xff08;master 分支&#xff09;&#xff1a;https://gitee.com/dye_your_fingers/titan…

HBase 的安装与部署

目录 1 启动 zookeeper2 启动 Hadoop3 HBase 的安装与部署4 HBase 高可用 1 启动 zookeeper [huweihadoop101 ~]$ bin/zk_cluster.sh start2 启动 Hadoop [huweihadoop101 ~]$ bin/hdp_cluster.sh start3 HBase 的安装与部署 &#xff08;1&#xff09;将 hbase-2.0.5-bin.tar.…

探索设计模式的魅力:深入解析解释器模式-学习、实现与高效使用的全指南

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;并且坚持默默的做事。 探索设计模式的魅力&#xff1a;解析解释器模式学习、实现与高效使用全指南 文章目录 一、案…

06.Promise的状态和基本使用

一.认识Promise 1. 什么是 Promise &#xff1f; Promise 对象用于表示一个异步操作的最终完成&#xff08;或失败&#xff09;及其结构值 2. Promise 的好处是什么&#xff1f; 逻辑更清晰&#xff08;成功或失败会关联后续的处理函数&#xff09; 了解 axios 函数内部运作…

基于Python实现银行卡识别

在本文中将介绍如何使用Python和深度学习技术来实现银行卡识别功能。银行卡识别是一个在金融、安全等领域具有重要应用的问题&#xff0c;将使用深度学习模型来实现银行卡图像的识别和分类。 目录 引言数据集准备预处理和特征提取模型选择与训练模型评估与性能优化部署与应用 引…