算法打卡day15|二叉树篇04|110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和

2024-03-13 08:20

本文主要是介绍算法打卡day15|二叉树篇04|110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 算法题

Leetcode  110.平衡二叉树

题目链接:110.平衡二叉树

大佬视频讲解:平衡二叉树视频讲解

个人思路

可以用递归法,计算左右子树的高度差,当超过1时就不为平衡二叉树了;

解法

回顾一下二叉树节点的深度与高度;

  • 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数。
  • 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数。

在leetcode中深度从1开始的,有些地方从0开始;

递归法

类似于二叉树的后序遍历,即对于当前遍历到的节点:先递归地判断其左右子树是否平
衡,
再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的,则返回其高度(高度一定
是非负整数),否则返回 -1。如果存在一棵子树不平衡,则整个二叉树一定不平衡。

如果是用前序遍历,则对于同一个节点,函数 getHeight 会被重复调用,导致时间复杂
度较高。如果使用后序遍历的做法,则对于每个节点,函数 height 只会被调用一次。

也可以这样记忆,当树节点高度与深度不同时,求深度可以从上到下去查 所以需要前序遍历(中左右),而高度只能从下到上去查,所以只能后序遍历(左右中)

class Solution {public boolean isBalanced(TreeNode root) {//1.确定递归函数参数以及返回值return getHeight(root) != -1;//判断是否为平衡二叉树}private int getHeight(TreeNode root) {if (root == null) {//根;前序遍历,先遍历根;return 0;}//3.确定单层递归逻辑int leftHeight = getHeight(root.left);//左if (leftHeight == -1) {return -1;}int rightHeight = getHeight(root.right);//右if (rightHeight == -1) {return -1;}// 左右子树高度差大于1,return -1表示已经不是平衡树了if (Math.abs(leftHeight - rightHeight) > 1) {//2.确定递归终止条件return -1;}return Math.max(leftHeight, rightHeight) + 1;}
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(使用二叉树)

迭代法

来模拟后序遍历,遍历每一个节点的时候,再去判断左右孩子的高度是否符合,其中利用TreeNode.val来保存当前结点的高度,这样就不会有重复遍历;

class Solution {public boolean isBalanced(TreeNode root) {if (root == null) {return true;}Stack<TreeNode> stack = new Stack<>();TreeNode pre = null;while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;}TreeNode inNode = stack.peek();// 右结点为null或已经遍历过if (inNode.right == null || inNode.right == pre) {// 输出if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) {return false;}stack.pop();pre = inNode;root = null;// 当前结点下,没有要遍历的结点了} else {root = inNode.right;// 右结点还没遍历,遍历右结点}}return true;}// 求结点的高度public int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = root.left != null ? root.left.val : 0;int rightHeight = root.right != null ? root.right.val : 0;int height = Math.max(leftHeight, rightHeight) + 1;root.val = height;// 用TreeNode.val来保存当前结点的高度return height;}
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(一个栈的空间,最差情况下与树的空间一样,那就是n)


Leetcode 257. 二叉树的所有路径

题目链接:257. 二叉树的所有路径

大佬视频讲解:二叉树的所有路径视频讲解

个人思路

就知道好像是用回溯,但不记得怎么实现了

解法
递归法

要求从根节点到叶子的路径,所以需要前序遍历,这样才方便让父节点指向孩子节点,找到对应的路径,因为要返回根到叶子结点的路径,所以肯定是需要回溯的,递归和回溯就是一家的;

因为是要记录到叶子节点的路径,所以左右孩子为空则为终止条件,到遍历到叶子节点,则将结果打印放入数组,然后回溯继续递归;

在写代码时,要记住回溯和递归是一一对应的,有一个递归,就要有一个回溯

class Solution {public List<String> binaryTreePaths(TreeNode root) {//1.确定递归函数参数以及返回值List<String> res = new ArrayList<>();// 存最终的结果if (root == null) {return res;}List<Integer> paths = new ArrayList<>();// 作为结果中的路径traversal(root, paths, res);return res;}private void traversal(TreeNode root, List<Integer> paths, List<String> res) {paths.add(root.val);// 前序遍历,中// 遇到叶子结点if (root.left == null && root.right == null) {//2.确定递归终止条件// 输出StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串for (int i = 0; i < paths.size() - 1; i++) {sb.append(paths.get(i)).append("->");}sb.append(paths.get(paths.size() - 1));// 记录最后一个节点res.add(sb.toString());// 收集一个路径return;}//3.确定单层递归逻辑// 递归和回溯是同时进行,所以要放在同一个花括号里if (root.left != null) { // 左traversal(root.left, paths, res);//有一个递归,就要有一个回溯paths.remove(paths.size() - 1);// 回溯}if (root.right != null) { // 右traversal(root.right, paths, res);//有一个递归,就要有一个回溯paths.remove(paths.size() - 1);// 回溯}}
}

时间复杂度:O(n^2);(每遍历一条路径都要拷贝数据,高度乘节点,所以是n*n)

空间复杂度:O(n^2);(递归遍历暂存字符与结果,都需要空间)

迭代法

使用前序遍历的迭代方式来模拟遍历路径的过程


class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();if (root == null)return result;Stack<Object> stack = new Stack<>();// 节点和路径同时入栈stack.push(root);stack.push(root.val + "");while (!stack.isEmpty()) {// 节点和路径同时出栈String path = (String) stack.pop();TreeNode node = (TreeNode) stack.pop();// 若找到叶子节点if (node.left == null && node.right == null) {result.add(path);}//右子节点不为空if (node.right != null) {stack.push(node.right);stack.push(path + "->" + node.right.val);}//左子节点不为空if (node.left != null) {stack.push(node.left);stack.push(path + "->" + node.left.val);}}return result;}
}

时间复杂度:O(n^2);(每遍历一条路径都要拷贝数据)

空间复杂度:O(n);(使用两个栈,一个存数据,一个遍历)


Leetcode 404.左叶子之和

题目链接:404.左叶子之和

大佬视频讲解:左叶子之和视频讲解

个人思路

可以用层序遍历,遍历到最后一层时,将左叶子筛选出来,结果值累加;

解法
递归法

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

递归三部曲

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

判断一个树的左叶子节点之和,那么一定要传入树的根节点,递归函数的返回值为数值之和,所以为int

2.确定终止条件

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

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

3.确定单层递归的逻辑

当遇到左叶子节点的时候,记录数值,然后通过递归求取左子树左叶子之和,和 右子树左叶子之和,相加便是整个树的左叶子之和。

class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root == null) return 0;int leftValue = sumOfLeftLeaves(root.left);    // 左int rightValue = sumOfLeftLeaves(root.right);  // 右int midValue = 0;//判断是否为左叶子节点if (root.left != null && root.left.left == null && root.left.right == null) { midValue = root.left.val;}int sum = midValue + leftValue + rightValue;  // 中return sum;}
}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(n);(递归栈)

迭代法

层序遍历迭代法,采用前序遍历,在模板代码的基础上判断当前节点的子节点是否左叶子,并累加值;

class Solution {public int sumOfLeftLeaves(TreeNode root) {int sum = 0;//左叶子节点和if (root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();while (size -- > 0) {TreeNode node = queue.poll();//判断是否为左叶子节点if (node.left != null) { // 左节点不为空queue.offer(node.left);if (node.left.left == null && node.left.right == null){ // 左叶子节点sum += node.left.val;}}if (node.right != null) queue.offer(node.right);}}return sum;}
}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(n);(使用队列)

以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网代码随想录算法官网代码随想录算法官网

这篇关于算法打卡day15|二叉树篇04|110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

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文件的位置接下来从高级-

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

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

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Python如何调用指定路径的模块

《Python如何调用指定路径的模块》要在Python中调用指定路径的模块,可以使用sys.path.append,importlib.util.spec_from_file_location和exe... 目录一、sys.path.append() 方法1. 方法简介2. 使用示例3. 注意事项二、imp

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL