当前位置: 首页 > news >正文

多种方法解决leetcode经典题目-LCR 155. 将二叉搜索树转化为排序的双向链表, 同时弄透引用变更带来的bug

1 描述

在这里插入图片描述

2 解法一: 使用list列表粗出中序遍历的结果,然后再依次处理list中的元素并且双向链接

public Node treeToDoublyList2(Node root) {if(root==null)return root;Node dummy=new Node(-10000);List<Node>ans=new ArrayList<>();dfs2(root,ans);Node pre=ans.get(0);dummy.right=pre;for(int i=1;i<ans.size();i++){Node cur=ans.get(i);pre.right=cur;cur.left=pre;pre=cur;}dummy.right.left=pre;pre.right=dummy.right;return dummy.right;}void dfs2(Node root, List<Node>ans){if(root==null){return;}dfs2(root.left,ans);ans.add(root);dfs2(root.right,ans);}

3 解法二:使用一个全局变量作为前驱节点,同时使用一个虚拟头节点指向这个前驱,在使用dfs的时候进行双向链接,然后通过dummy虚拟头节点完成链表循环

	Node pre;public Node treeToDoublyList(Node root) {if(root==null)return root;Node dummy=new Node(-10000);pre=dummy;dfs(root);pre.right=dummy.right;dummy.right.left=pre;return dummy.right;}void dfs(Node root){if(root==null){return;}dfs(root.left);pre.right=root;root.left=pre;pre=root;dfs(root.right);}

4 解法三:通过引用传递

4.1 版本一:数组引用传递(执行无误)

    public Node treeToDoublyList(Node root) {if(root==null)return root;Node dummy=new Node(-10000);Node prev[]=new Node[1];prev[0]=new Node(100001);dummy=prev[0];dfs4(root,prev);prev[0].right=dummy.right;dummy.right.left=prev[0];return dummy.right;}void dfs4(Node root,Node[] prev){if(root==null){return;}dfs4(root.left,prev);prev[0].right=root;root.left=prev[0];prev[0]=root;dfs4(root.right,prev);}

4.2 版本二:通过变量引用传递(但是执行起来有问题)

public Node treeToDoublyList(Node root) {if(root==null)return root;Node dummy=new Node(-10000);Node pre=dummy;dfs(root);pre.right=dummy.right;dummy.right.left=pre;return dummy.right;}void dfs3(Node root,Node pre){if(root==null){return;}dfs3(root.left,pre);pre.right=root;root.left=pre;pre=root;dfs3(root.right,pre);}

4.3 比较一下版本1和2,2中哪里出错了,为什么错了?

这段代码实际上是一个常见的算法题目的解法,目标是将一个二叉搜索树转换为一个排序的双向链表。整个过程是通过中序遍历来实现的,遍历过程中修改节点的左右指针来构建双向链表。代码中使用了一个额外的节点 dummy 来帮助构建双向链表,并使用 pre 节点来保存前一个遍历到的节点。

代码中的错误主要在 dfs3 方法中,pre 节点作为参数传递,但在递归调用中并没有更新 pre 的值。这会导致链表构建不正确。要修复这个问题,你需要在 dfs3 方法中更新 pre 的值。下面是修正后的 dfs3 方法:

void dfs3(Node root,Node[] pre){if(root==null){return;}dfs3(root.left,pre);pre[0].right=root;root.left=pre[0];pre[0]=root;dfs3(root.right,pre);
}

调用 dfs3 方法时,你需要传递一个 Node 类型数组作为 pre 参数,例如:

Node[] pre = new Node[1];
pre[0] = dummy;
dfs3(root, pre);

这样,pre 数组中的元素会在 dfs3 方法中被正确更新,从而可以构建正确的双向链表。

4.4 这里的Node pre是作为值传递的嘛?你改为传递长度为1的Node数组,就变成了引用传递?

在Java中,对象的引用是通过值传递的。这意味着当你将一个对象作为参数传递给一个方法时,你实际上是将对象引用的副本传递给了方法。如果你在方法内部修改引用所指向的对象的状态,这个修改会反映到方法外部。但是,如果你尝试直接修改引用本身(例如,使其指向一个新的对象),这个修改不会影响到方法外部的引用。

在你的代码中,Node pre 是一个对象引用,当你将其作为参数传递给 dfs3 方法时,你传递的是引用的副本。在 dfs3 方法内部,你可以修改 pre 引用所指向的 Node 对象的状态,但是如果你尝试直接修改 pre 引用本身(例如,pre = new Node(…), pre = root),这个修改不会影响到方法外部的 pre 引用。

为了在 dfs3 方法内部更新外部的 pre 引用,你可以使用一个 Node 类型的数组,如我之前所示。数组在Java中是一个对象,当你将数组作为参数传递给一个方法时,你传递的是数组对象引用的副本。你可以在方法内部修改数组内容,这些修改会反映到方法外部。因此,你可以使用一个数组来包装 pre 引用,然后在 dfs3 方法内部更新数组的内容,这样就能够实现在方法调用后更新外部的 pre 引用。

相关文章:

多种方法解决leetcode经典题目-LCR 155. 将二叉搜索树转化为排序的双向链表, 同时弄透引用变更带来的bug

1 描述 2 解法一: 使用list列表粗出中序遍历的结果&#xff0c;然后再依次处理list中的元素并且双向链接 public Node treeToDoublyList2(Node root) {if(rootnull)return root;Node dummynew Node(-10000);List<Node>ansnew ArrayList<>();dfs2(root,ans);Node p…...

C/C++ 实现UDP发送或接收组播消息,并可指定接收发送网卡

一、发送端代码 #include <iostream> #include <unistd.h> #include <stdio.h> #include <string.h> #include <net/if.h> #include <netinet/in.h> #include <netdb.h> #include <sys/ioctl.h> #include "UDPOperation…...

纬创出售印度子公司给塔塔集团,结束iPhone代工业务 | 百能云芯

纬创&#xff08;Wistron&#xff09;董事会于10月27日通过决议&#xff0c;同意以1.25亿美元的价格出售其印度子公司Wistron InfoComm Manufacturing (India) Private Limited&#xff08;WMMI&#xff09;的100%股权给塔塔集团&#xff0c;交割将尽快完成。此举将意味着纬创退…...

vue手机项目如何控制手电筒打开与关闭

要控制手电筒&#xff0c;您可以使用Vue的Device API&#xff0c;例如cordova-plugin-flashlight或vue-native-flashlight插件。以下是一些基本步骤&#xff1a; 导入手电筒插件或库。在Vue组件中创建一个手电筒对象并初始化它。使用turnOn()和turnOff()方法控制手电筒。 以下…...

电商课堂|5分钟了解电商数据分析完整流程,建议收藏!

账户效果下降&#xff0c;如何能够快速找到问题并优化调整&#xff1f; 相信百分之90%的竞价员都会说&#xff1a;“做数据分析。” 没错&#xff0c;数据分析能够帮助我们快速锁定问题所在&#xff0c;确定优化方向&#xff0c;还可以帮助我们找到流量控制的方向。那么做电商&…...

Redis测试新手入门教程

在测试过程中&#xff0c;我们或多或少会接触到Redis&#xff0c;今天就把在小破站看到的三丰老师课程&#xff0c;把笔记整理了下&#xff0c;用来备忘&#xff0c;也希望能给大家带来亿点点收获。 主要分为两个部分&#xff1a; 一、缓存技术在后端架构中是如何应用的&#…...

Linux内核是如何创建进程?

目录 1.Linux如何创建进程 2.fork函数原理 2.1 fork函数原型 2.2 fork函数实现原理 2.3 父子进程虚拟地址空间&#xff08;mm_struct&#xff09;之间的关系 2.4 写时拷贝&#xff08;copy-on-write&#xff09;技术 2.5 父子进程如何共享文件&#xff08;files_struct&…...

IDEA 使用技巧

文章目录 语言支持简化编写 有问题&#xff0c;可暂时跳过 个人常用快捷键插件主题插件功能插件 碰到过的问题 除了一些在Linux上用vim开发的大佬&#xff0c;idea算是很友好的集成开发工具了&#xff0c;功能全面&#xff0c;使用也很广泛。 记录一下我的 IDEA 使用技巧&#…...

安防监控项目---web网页通过A9控制Zigbee终端节点的风扇

文章目录 前言一、zigbee的CGI接口二、请求线程和硬件控制三、现象展示总结 前言 书接上期&#xff0c;我们可以看一下前面的功能设计的部分&#xff0c;网页端的控制还有一个&#xff0c;那就是通过网页来控制zigbee上的风扇节点&#xff0c;这部分的工作量是相当大的&#x…...

Ubuntu 22.04 在登录界面循环

问题描述 https://blog.csdn.net/weixin_44023406/article/details/134092271?spm1001.2014.3001.5502 接上一篇&#xff0c;磁盘满了&#xff0c;扩展空间之后能正常开机&#xff0c;进到登录界面&#xff0c;输密码3秒后又回到登录界面 分析解决问题 命令行能登录&#…...

【C++ 系列文章 -- 程序员考试 201805 下午场 C++ 专题 】

文章目录 1.1 C 题目六1.1.1 填空&#xff08;1&#xff09;详解1.1.1.1 C 纯虚函数介绍 1.1.2 填空&#xff08;2&#xff09;详解1.1.2.1 父类声明了带参构造函数1.1.2.2 子类中构造函数的构造原则 1.1.3 填空&#xff08;3&#xff09;详解1.1.4 填空&#xff08;4&#xff…...

Python如何使用datetime模块进行日期和时间的操作

目录 一、引言 二、datetime模块的基本使用 三、日期的运算 四、注意事项 总结 本文将对Python的datetime模块进行深入探讨&#xff0c;阐述如何使用该模块进行日期和时间的各种操作。我们将介绍日期和时间的基本操作&#xff0c;以及格式化、时区处理等高级操作&#xff…...

flutter之bloc使用详解

flutter中一切皆为Widget&#xff0c;因此在我们开发中&#xff0c;往往业务和UI逻辑写在一起&#xff0c;这样不利于代码维护&#xff0c;因此状态管理框架久诞生了&#xff0c;这篇就开始讲一讲Bloc。 对于Bloc库有两个&#xff0c;如下图&#xff1a; flutter_bloc其实是对…...

记一次 .NET 某工厂无人车调度系统 线程爆高分析

一&#xff1a;背景 1. 讲故事 前些天有位朋友找到我&#xff0c;说他程序中的线程数爆高&#xff0c;让我帮忙看下怎么回事&#xff0c;这种线程数爆高的情况找问题相对比较容易&#xff0c;就让朋友丢一个dump给我&#xff0c;看看便知。 二&#xff1a;为什么会爆高 1. …...

高等数学啃书汇总重难点(九)多元函数微分法及其应用

下册最重要也是个人认为偏恶心的一节&#xff08;主要东西是真不少....&#xff09;重点在于会计算偏导、能理解全微分及隐函数求导3个核心内容&#xff0c;至于后面的关于几何层面的应用&#xff0c;建议掌握计算方法即可&#xff0c;学有余力再死磕推导过程等内容~ 1.平面点集…...

Vue3前端100个必要的知识点

为什么是必要的&#xff0c;就是这100个知识点学完后&#xff0c;能独立完成一个小项目。最终能得到一个解决方案。也算是前端知识的积累。如果后面有需要的地方可以回来查。100个其实比较多&#xff0c;我会按新手老鸟&#xff0c;大神来分成3个等级&#xff0c;话不多说&…...

CCS3列表和超链接样式

在默认状态下&#xff0c;超链接文本显示为蓝色、下画线效果&#xff0c;当鼠标指针移过超链接时显示为手形&#xff0c;访问过的超链接文本显示为紫色&#xff1b;而列表项目默认会缩进显示&#xff0c;并在左侧显示项目符号。在网页设计中&#xff0c;一般可以根据需要重新定…...

vue手机项目如何控制蓝牙连接

要控制蓝牙连接&#xff0c;您需要使用Vue的蓝牙插件或库&#xff0c;例如BLE-Peripheral或cordova-plugin-ble-central。以下是一些基本步骤&#xff1a; 导入蓝牙插件或库。在Vue组件中创建一个蓝牙对象并初始化它。扫描周围的蓝牙设备并连接到所需的设备。一旦连接成功&…...

遥遥领先,免费开源的django4-vue3项目

星域后台管理系统前端介绍 &#x1f33f;项目简介 本项目前端基于当下流行且常用的vue3作为主要技术栈进行开发&#xff0c;融合了typescript和element-plus-ui&#xff0c;提供暗黑模式和白昼模式两种主题以及全屏切换&#xff0c;开发bug少&#xff0c;简单易学&#xff0c…...

视频平台跨网级联视频压缩解决方案

一、 简介 视频监控领域对带宽有着较大的需求&#xff0c;这是因为视频流需要实时占用网络带宽资源。视频监控的传输带宽是组网结构的基础保障&#xff0c;关系到视频监控的稳定性、可靠性和可拓展性等因素。例如&#xff0c;720P的视频格式每路摄像头的比特率为2Mbps&#xff…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...