To Future$ - Java
type: channel
link: https://blog.lvming.xin/index.php/tag/Java/
items: java 补全之「网络编程」
items: java 补全之「IO」
items: java 补全之「java 核心类」
items: java 补全之「面向对象编程基础」
items: Java Web 基础：登录认证-会话技术、过滤器与拦截器、事务管理
items: LeetCode 42. 接雨水 [Hot 100] —— DP/双指针
items: LeetCode 438. 找到字符串中所有字母异位词 [Hot 100]
items: 递归返回值使用模式总结
items: LeetCode 236. 二叉树的最近公共祖先 [Hot 100]
items: LeetCode 114. 二叉树展开为链表 [Hot 100]

java 补全之「网络编程」
type: item
date: 2026-01-08T15:01:00+08:00
description: 网络编程1.网络编程基础在学习Java网络编程之前，我们先来了解什么是计算机网络。计算机网络是指两台或更多的计算机组成的网络，在同一个网络中，任意两台计算机都可以直接通信，因为所有计算机都需要遵循同一种网络协议。那什么是互联网呢？互联网是网络的网络（Internet），即把很多计算机网络连接起来，形成一个全球统一的互联网。对某个特定的计算机网络来说，它可能使用网络协议ABC，而另一个计算机网络可能使用网络协议XYZ。如果计算机网络各自的通讯协议不统一，就没法把不同的网络连接起来形成互联网。因此，为了把计算机网络接入互联网，就必须使用TCP/IP协议。TCP/IP协议泛指互联网协议，其中最重要的两个协议是TCP协议和IP协议。只有使用TCP/IP协议的计算机才能够联入互联网，使用其他网络协议（例如NetBIOS、AppleTalk协议等）是无法联入互联网的。IP地址在互联网中，一个IP地址用于唯一标识一个网络接口（Network Interface）。一台联入互联网的计算机肯定有一个IP地址，但也可能有多个IP地址。IP地址分为IPv4和IPv6两种。IPv4采用32位地址，类似101.202.99.12，而IPv6采用128位地址，类似2001:0DA8:100A:0000:0000:1020:F2F3:1428。IPv4地址总共有232个（大约42亿），而IPv6地址则总共有2128个（大约340万亿亿亿亿），IPv4的地址目前已耗尽，而IPv6的地址是根本用不完的。IP地址又分为公网IP地址和内网IP地址。公网IP地址可以直接被访问，内网IP地址只能在内网访问。内网IP地址类似于：192.168.x.x10.x.x.x有一个特殊的IP地址，称之为本机地址，它总是127.0.0.1。IPv4地址实际上是一个32位整数。例如：1707762444 = 0x65ca630c = 65 ca 63 0c = 101.202.99.12如果一台计算机只有一个网卡，并且接入了网络，那么，它有一个本机地址127.0.0.1，还有一个IP地址，例如101.202.99.12，可以通过这个IP地址接入网络。如果一台计算机有两块网卡，那么除了本机地址，它可以有两个IP地址，可以分别接入两个网络。通常连接两个网络的设备是路由器或者交换机，它至少有两个IP地址，分别接入不同的网络，让网络之间连接起来。如果两台计算机位于同一个网络，那么他们之间可以直接通信，因为他们的IP地址前段是相同的，也就是网络号是相同的。网络号是IP地址通过子网掩码过滤后得到的。例如：某台计算机的IP是101.202.99.2，子网掩码是255.255.255.0，那么计算该计算机的网络号是：IP = 101.202.99.2 Mask = 255.255.255.0 Network = IP & Mask = 101.202.99.0每台计算机都需要正确配置IP地址和子网掩码，根据这两个就可以计算网络号，如果两台计算机计算出的网络号相同，说明两台计算机在同一个网络，可以直接通信。如果两台计算机计算出的网络号不同，那么两台计算机不在同一个网络，不能直接通信，它们之间必须通过路由器或者交换机这样的网络设备间接通信，我们把这种设备称为网关。网关的作用就是连接多个网络，负责把来自一个网络的数据包发到另一个网络，这个过程叫路由。所以，一台计算机的一个网卡会有3个关键配置：IP地址，例如：10.0.2.15子网掩码，例如：255.255.255.0网关的IP地址，例如：10.0.2.2域名因为直接记忆IP地址非常困难，所以我们通常使用域名访问某个特定的服务。域名解析服务器DNS负责把域名翻译成对应的IP，客户端再根据IP地址访问服务器。用nslookup可以查看域名对应的IP地址：$ nslookup liaoxuefeng.com Server: xxx.xxx.xxx.xxx Address: xxx.xxx.xxx.xxx#53 Non-authoritative answer: Name: liaoxuefeng.com Address: xxx.xxx.xxx.xxx有一个特殊的本机域名localhost，它对应的IP地址总是本机地址127.0.0.1。网络模型由于计算机网络从底层的传输到高层的软件设计十分复杂，要合理地设计计算机网络模型，必须采用分层模型，每一层负责处理自己的操作。OSI（Open System Interconnect）网络模型是ISO组织定义的一个计算机互联的标准模型，注意它只是一个定义，目的是为了简化网络各层的操作，提供标准接口便于实现和维护。这个模型从上到下依次是：应用层，提供应用程序之间的通信；表示层：处理数据格式，加解密等等；会话层：负责建立和维…

java 补全之「IO」
type: item
date: 2026-01-06T21:20:00+08:00
description: IO1.File对象在计算机系统中，文件是非常重要的存储方式。Java的标准库java.io提供了File对象来操作文件和目录。要构造一个File对象，需要传入文件路径：import java.io.*; public class Main { public static void main(String[] args) { File f = new File("C:\\Windows\\notepad.exe"); System.out.println(f); } }构造File对象时，既可以传入绝对路径，也可以传入相对路径。绝对路径是以根目录开头的完整路径，例如：File f = new File("C:\\Windows\\notepad.exe");注意Windows平台使用\作为路径分隔符，在Java字符串中需要用\\表示一个\。Linux平台使用/作为路径分隔符：File f = new File("/usr/bin/javac");传入相对路径时，相对路径前面加上当前目录就是绝对路径：// 假设当前目录是C:\Docs File f1 = new File("sub\\javac"); // 绝对路径是C:\Docs\sub\javac File f3 = new File(".\\sub\\javac"); // 绝对路径是C:\Docs\sub\javac File f3 = new File("..\\sub\\javac"); // 绝对路径是C:\sub\javac可以用.表示当前目录，..表示上级目录。File对象有3种形式表示的路径，一种是getPath()，返回构造方法传入的路径，一种是getAbsolutePath()，返回绝对路径，一种是getCanonicalPath，它和绝对路径类似，但是返回的是规范路径。什么是规范路径？我们看以下代码：import java.io.*; public class Main { public static void main(String[] args) throws IOException { File f = new File(".."); System.out.println(f.getPath()); System.out.println(f.getAbsolutePath()); System.out.println(f.getCanonicalPath()); } }绝对路径可以表示成C:\Windows\System32\..\notepad.exe，而规范路径就是把.和..转换成标准的绝对路径后的路径：C:\Windows\notepad.exe。因为Windows和Linux的路径分隔符不同，File对象有一个静态变量用于表示当前平台的系统分隔符：System.out.println(File.separator); // 根据当前平台打印"\"或"/"文件和目录File对象既可以表示文件，也可以表示目录。特别要注意的是，构造一个File对象，即使传入的文件或目录不存在，代码也不会出错，因为构造一个File对象，并不会导致任何磁盘操作。只有当我们调用File对象的某些方法的时候，才真正进行磁盘操作。例如，调用isFile()，判断该File对象是否是一个已存在的文件，调用isDirectory()，判断该File对象是否是一个已存在的目录：import java.io.*; public class Main { public static void main(String[] args) throws IOException { File f1 = new File("C:\\Windows"); File f2 = new File("C:\\Windows\\notepad.exe"); File f3 = new File("C:\\Windows\\nothing"); System.out.println(f1.isFile()); System.out.println(f1.isDirectory()); System.out.println(f2.isFile()); System.out.println(f2.isDirectory()); System.out.println(f3.isFile()); System.out.println(f3.isDirectory()); } }用File对象获取到一个文件时，还可以进一步判断文件的权限和大小：boolean canRead()：是否可读；boolean canWrite()：是否可写；boolean canExecute()：是否可执行；long length(…

java 补全之「java 核心类」
type: item
date: 2026-01-06T15:01:00+08:00
description: 面向对象编程-java核心类1.字符串字符串比较当我们想要比较两个字符串是否相同时，要特别注意，我们实际上是想比较字符串的内容是否相同。必须使用equals()方法而不能用==。我们看下面的例子：// String public class Main { public static void main(String[] args) { String s1 = "hello"; String s2 = "hello"; System.out.println(s1 == s2); System.out.println(s1.equals(s2)); } }从表面上看，两个字符串用==和equals()比较都为true，但实际上那只是Java编译器在编译期，会自动把所有相同的字符串当作一个对象放入常量池，自然s1和s2的引用就是相同的。所以，这种==比较返回true纯属巧合。换一种写法，==比较就会失败：// String public class Main { public static void main(String[] args) { String s1 = "hello"; String s2 = "HELLO".toLowerCase(); System.out.println(s1 == s2); System.out.println(s1.equals(s2)); } }结论：两个字符串比较，必须总是使用equals()方法。要忽略大小写比较，使用equalsIgnoreCase()方法。字符串编辑：去除首尾空白字符、提取子串、替换子串、分割字符串、拼接字符串使用trim()方法可以移除字符串首尾空白字符。空白字符包括空格，\t，\r，\n：" \tHello\r\n ".trim(); // "Hello"注意：trim()并没有改变字符串的内容，而是返回了一个新字符串。另一个strip()方法也可以移除字符串首尾空白字符。它和trim()不同的是，类似中文的空格字符\u3000也会被移除："\u3000Hello\u3000".strip(); // "Hello" " Hello ".stripLeading(); // "Hello " " Hello ".stripTrailing(); // " Hello"String还提供了isEmpty()和isBlank()来判断字符串是否为空和空白字符串："".isEmpty(); // true，因为字符串长度为0 " ".isEmpty(); // false，因为字符串长度不为0 " \n".isBlank(); // true，因为只包含空白字符 " Hello ".isBlank(); // false，因为包含非空白字符String类还提供了多种方法来搜索子串、提取子串。常用的方法有：// 是否包含子串: "Hello".contains("ll"); // true注意到contains()方法的参数是CharSequence而不是String，因为CharSequence是String实现的一个接口。搜索子串的更多的例子："Hello".indexOf("l"); // 2 "Hello".lastIndexOf("l"); // 3 "Hello".startsWith("He"); // true "Hello".endsWith("lo"); // true提取子串的例子："Hello".substring(2); // "llo" "Hello".substring(2, 4); "ll"要在字符串中替换子串，有两种方法。一种是根据字符或字符串替换：String s = "hello"; s.replace('l', 'w'); // "hewwo"，所有字符'l'被替换为'w' s.replace("ll", "~~"); // "he~~o"，所有子串"ll"被替换为"~~"另一种是通过正则表达式替换：String s = "A,,B;C ,D"; s.replaceAll("[\\,\\;\\s]+", ","); // "A,B,C,D"上面的代码通过正则表达式，把匹配的子串统一替换为","。关于正则表达式的用法我们会在后面详细讲解。要分割字符串，使用split()方法，并且传入的也是正则表达式：String s = "A,B,C,D"; String[] ss = s.split("\\,"); // {"A", "B", "C", "D"}拼接字符串使用静态方法join()，它用指定的字符串连接字符串数组：String[] arr = {"A", "B", "C"}; S格式化字符串字符串提供了formatted()方法和fo…

java 补全之「面向对象编程基础」
type: item
date: 2026-01-06T00:25:00+08:00
description: 面向对象编程-面向对象编程基础1.继承--super()的注意事项我们来看一个例子：// super public class Main { public static void main(String[] args) { Student s = new Student("Xiao Ming", 12, 89); } } class Person { protected String name; protected int age; public Person(String name, int age) { this.name = name; this.age = age; } } class Student extends Person { protected int score; public Student(String name, int age, int score) { this.score = score; } }运行上面的代码，会得到一个编译错误，大意是在Student的构造方法中，无法调用Person的构造方法。这是因为在Java中，任何class的构造方法，第一行语句必须是调用父类的构造方法。如果没有明确地调用父类的构造方法，编译器会帮我们自动加一句super();所以，Student类的构造方法实际上是这样：class Student extends Person { protected int score; public Student(String name, int age, int score) { super(); // 自动调用父类的构造方法 this.score = score; } }但是，Person类并没有无参数的构造方法，因此，编译失败。解决方法是调用Person类存在的某个构造方法。例如：class Student extends Person { protected int score; public Student(String name, int age, int score) { super(name, age); // 调用父类的构造方法Person(String, int) this.score = score; } }这样就可以正常编译了！在子类的覆写方法中，如果要调用父类的被覆写的方法，可以通过super来调用。例如：class Person { protected String name; public String hello() { return "Hello, " + name; } } class Student extends Person { @Override public String hello() { // 调用父类的hello()方法: return super.hello() + "!"; } }2.继承-阻止继承final修饰符有多种作用：final修饰的方法可以阻止被覆写；final修饰的class可以阻止被继承；final修饰的field必须在创建对象时初始化，随后不可修改。从Java 15开始，允许使用sealed修饰class，并通过permits明确写出能够从该class继承的子类名称。例如，定义一个Shape类：public sealed class Shape permits Rect, Circle, Triangle { ... }上述Shape类就是一个sealed类，它只允许指定的3个类继承它。如果写：public final class Rect extends Shape {...}是没问题的，因为Rect出现在Shape的permits列表中。但是，如果定义一个Ellipse就会报错：public final class Ellipse extends Shape {...} // Compile error: class is not allowed to extend sealed class: Shape原因是Ellipse并未出现在Shape的permits列表中。这种sealed类主要用于一些框架，防止继承被滥用。sealed类在Java 15中目前是预览状态，要启用它，必须使用参数--enable-preview和--source 15。3.继承--向下转型向下转型很可能会失败。失败的时候，Java虚拟机会报ClassCastException。为了避免向下转型出错，Java提供了instanceof操作符，可以先判断一个实例究竟是不是某种类型：Person p = new Person(); System.out.println(p instanceof Person); // true Syst…

Java Web 基础：登录认证-会话技术、过滤器与拦截器、事务管理
type: item
date: 2025-10-09T17:07:15+08:00
description: 登录认证-会话技术会话：用户打开浏览器，访问web服务器的资源，会话建立，直到有一方断开连接，会话结束。在一次会话中可以包含多次请求和响应。会话跟踪：一种维护浏览器状态的方法，服务器需要识别多次请求是否来自于同意浏览器，以便在同一次会话的多次请求间共享数据。会话跟踪方案：客户端会话跟踪技术：Cookie服务端会话跟踪技术：Session令牌技术Cookie浏览器响应头 Set-Cookie:name=value客户端请求头 Cookie:name=value优点：Http协议支持缺点：移动端App无法使用Cookie；不安全，客户可以自己禁用Cookie；不能跨域（跨域：客户端和服务端协议/ip/域名/端口不同都会跨域）；【无状态】Session底层基于Cookie优点：状态存储在服务端端的内存中，安全；【状态性，Session方案的核心优势在于“状态性”。服务器端有一个“指挥中心”，它知道哪些会话是活跃的、哪些是有效的。它可以随时吊销任何会话的访问权限。】缺点：服务器集群环境下无法直接使用Session；Cookie的缺点状态性就是，服务器有存储用户信息，用户只要一个token，无状态就是，用户自己存着信息，无论是否加密令牌技术优点：支持PC端和移动端；解决集群环境下的认证问题；减轻服务器端存储压力1.解决扩展性，实现集群和分布式【多服务端】使用令牌技术的服务器端不存储任何数据。传统Session存储在单个服务器的内存中，Session的旧解决方案：通过Session复制（性能开销大）或持久化到中央数据库（如Redis）（引入单点依赖和网络延迟）来缓解，但非根本解决。令牌的解决方案：采用无状态设计。服务器不存储会话数据，用户状态自包含在令牌中。任何服务器实例只需验证令牌有效性即可处理请求，天然支持分布式集群与水平扩展。2.解决架构耦合，实现多平台通用【多客户端】Session通常与特定的服务器端技术栈（如Java Servlet、PHP、.NET）紧密耦合。它依赖于Cookie来传递Session ID，这限制了客户端的类型。而令牌（尤其是JWT）是一个开放标准，任何语言、任何平台都能生成和验证。它不依赖Cookie，可以通过HTTP Header（如 Authorization: Bearer <token>）轻松传递，这使得它适用于：原生手机App；API网关；不同域名的前端应用（解决跨域）；第三方登录（OAuth 2.0的核心）：你可以用一个令牌授权一个第三方应用访问你的部分资源，而无需提供用户名和密码3.空间换时间，解决查询性能问题【快】传统的session，即使使用Redis，每个请求都需要根据Session ID执行一次网络查询来获取用户数据。在高并发场景下，这会给中央存储带来巨大的压力和单点故障风险。而令牌技术：用户信息（如user_id, username）直接编码在令牌里，验证成功后即可直接使用，无需查询数据库。这用更大的网络传输量（令牌体积比Session ID大）换取了更低的服务器端延迟和负载。JWT不是一个简单的“加密Cookie”，而是一种更安全、更标准、更通用的无状态凭证机制。特性加密的Cookie（自研方案）JWT令牌（标准方案）1. 安全核心保密性。依赖加密算法隐藏内容。如果密钥泄露，一切皆空。完整性与验证。依赖数字签名证明真伪。Payload可公开读取，但无法篡改。签名密钥泄露是灾难性的，但内容本身不依赖加密。2. 标准化自定义的、私有的。格式和加解密方法由开发者自己定义。开放的、标准的。遵循RFC 7519标准，有固定的结构（Header.Payload.Signature），各语言都有现成库，互通性好。3. 验证方式服务器必须解密整个Cookie才能验证其有效性。服务器只需验证签名（一个数学计算），而不需要先解密整个令牌。验证通过后，可直接解码读取Payload。4. 内容可信度服务器解密后，直接信任其中的内容。服务器验证签名后，才信任其中的内容。这明确区分了“验证”和“信任”两个步骤。5. 适用边界通常与Web域名绑定，通过Cookie机制管理。协议无关、域无关。可用于任何类型的客户端（App、桌面应用）、任何API，不受同源策略限制。过滤器与拦截器1. 过滤器示例：记录请求耗时和字符编码// 使用 @WebFilter 注解或通过 FilterRegistrationBean 配置 @Component public class LoggingFilter implements Filter { @Override public void doFilter(ServletRequest request, ServletResponse response, FilterChain ch…

LeetCode 42. 接雨水 [Hot 100] —— DP/双指针
type: item
date: 2025-09-29T19:40:00+08:00
description: 42. 接雨水已解答算术评级: 6给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。示例 1：输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2：输入：height = [4,2,0,3,2,5] 输出：9第一种解法：动态规划（双数组法）核心思路：分别计算每个位置左侧的最大高度（left 数组）和右侧的最大高度（right 数组）对于每个位置，能接的雨水量取决于左右两侧最大高度中的较小值与当前位置高度的差值class Solution { public int trap(int[] height) { int n = height.length; int[] left = new int[n]; int[] right = new int[n]; for (int i = 0; i < n; i++) { if (i>0) left[i] = Math.max(left[i-1],height[i]); else left[i] = height[i]; } for (int i = n-1; i >= 0; i--) { if (i<n-1) right[i] = Math.max(right[i+1], height[i]); else right[i] = height[i]; } int ans = 0; for (int i = 1; i < n-1; i++) { int h = Math.min(left[i-1], right[i+1]); ans += h - height[i]; } // 或者 // for (int i = 1; i < n-1; i++) { // int h = Math.min(left[i], right[i]); // ans += h; // } return ans; } }第二种解法：双指针法核心思路：使用左右两个指针从两端向中间移动维护两个变量 preMax 和 nextMax，分别记录左侧和右侧已遍历的最大高度根据当前左右最大值的大小决定移动哪个指针，并计算当前位置能接的雨水量class Solution { public int trap(int[] height) { int n = height.length; int l = 0; int r = n - 1; int ans = 0; int preMax = 0; int nextMax = 0; while (l < r) { preMax = Math.max(preMax, height[l]); nextMax = Math.max(nextMax, height[r]); if (preMax < nextMax) { ans += preMax - height[l]; l++; } else { ans += nextMax - height[r]; r--; } } return ans; } }

LeetCode 438. 找到字符串中所有字母异位词 [Hot 100]
type: item
date: 2025-09-24T17:16:56+08:00
description: 438. 找到字符串中所有字母异位词已解答中等给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。示例 1:输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。示例 2:输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。思路不难，注意两个关键点：1.注意map里存的是Integer不是int，要使用equals比较Integer值，避免自动装箱带来的问题2.map.put(ch, map.getOrDefault(ch, 0) + 1);可以减少判断key是否存在class Solution { private boolean check(Map<Character, Integer> map, Map<Character, Integer> map1) { // 先检查大小是否一致，提高效率 if (map.size() != map1.size()) return false; for (Map.Entry<Character, Integer> entry : map1.entrySet()) { Character key = entry.getKey(); Integer value = entry.getValue(); // 使用equals比较Integer值，避免自动装箱带来的问题 if (!map.containsKey(key) || !map.get(key).equals(value)) { return false; } } return true; } public List<Integer> findAnagrams(String s, String p) { Map<Character, Integer> map = new HashMap<>(); Map<Character, Integer> map1 = new HashMap<>(); List<Integer> ans = new ArrayList<>(); int n1 = s.length(); int n2 = p.length(); if (n1 < n2) return ans; // 初始化p的字符计数map1 for (int i = 0; i < n2; i++) { char ch1 = p.charAt(i); map1.put(ch1, map1.getOrDefault(ch1, 0) + 1); } // 初始化第一个窗口的字符计数map for (int i = 0; i < n2; i++) { char ch = s.charAt(i); map.put(ch, map.getOrDefault(ch, 0) + 1); } // 检查初始窗口 if (check(map, map1)) { ans.add(0); } // 滑动窗口 for (int i = n2; i < n1; i++) { // 添加新字符 char ch = s.charAt(i); map.put(ch, map.getOrDefault(ch, 0) + 1); // 移除窗口最左侧字符 char ch1 = s.charAt(i - n2); int count = map.get(ch1); if (count == 1) { map.remove(ch1); } else { map.put(ch1, count - 1); } // 检查当前窗口 if (check(map, map1)) { ans.add(i - n2 + 1); } } return ans; } }

递归返回值使用模式总结
type: item
date: 2025-09-24T11:58:08+08:00
description: 递归返回值的核心作用递归返回值主要有以下几种使用模式：1. 传递结果型返回值特点：返回值直接就是最终结果场景示例：// 二叉树的最大深度 public int maxDepth(TreeNode root) { if (root == null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; // 返回值就是深度结果 } // 斐波那契数列 public int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n-1) + fibonacci(n-2); // 直接返回计算结果 }适用场景：计算数值结果、判断布尔条件、返回对象等2. 状态标记型返回值特点：返回值作为状态标志，配合全局变量或参数使用场景示例：// 二叉树的最近公共祖先（LCA问题） public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return null; if (root == p || root == q) return root; // 返回找到的节点作为标记 TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) return root; // 组合状态判断 return left != null ? left : right; // 传递状态 }适用场景：查找问题、路径判断、状态传递3. 辅助计算型返回值特点：返回值用于辅助主逻辑，不是最终结果场景示例：// 平衡二叉树判断（返回高度辅助判断） private int checkBalance(TreeNode root) { if (root == null) return 0; int left = checkBalance(root.left); if (left == -1) return -1; // 用-1标记不平衡 int right = checkBalance(root.right); if (right == -1) return -1; if (Math.abs(left - right) > 1) return -1; return Math.max(left, right) + 1; // 返回高度辅助上层判断 } public boolean isBalanced(TreeNode root) { return checkBalance(root) != -1; }适用场景：需要中间计算结果的复杂判断4. 累积型返回值特点：返回值在递归过程中不断累积场景示例：// 路径总和（累积路径值） public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; // 叶子节点且路径和等于目标值 if (root.left == null && root.right == null) { return root.val == targetSum; } // 累积减去当前值，传递给子树 return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); }适用场景：路径和、累积计算、参数传递5. 构造型返回值特点：返回值是新建的数据结构场景示例：// 根据遍历序列构建二叉树 public TreeNode buildTree(int[] preorder, int[] inorder) { return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1); } private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) { if (preStart > preEnd) return null; TreeNod…

LeetCode 236. 二叉树的最近公共祖先 [Hot 100]
type: item
date: 2025-09-24T11:54:26+08:00
description: 236. 二叉树的最近公共祖先中等给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”示例 1：输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2：输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3：输入：root = [1,2], p = 1, q = 2 输出：1代码实现class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 递归终止条件 if (root == null) return null; if (root == p || root == q) return root; // 递归左右子树 TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); // 情况1：左右子树分别包含p和q，当前root就是LCA if (left != null && right != null) { return root; } // 情况2：只有左子树包含p或q if (left != null) { return left; } // 情况3：只有右子树包含p或q if (right != null) { return right; } // 情况4：左右子树都不包含p和q return null; } }递归法（后序遍历）核心思想：从底向上遍历（后序遍历）如果当前节点是 p 或 q，则返回该节点如果左右子树分别包含 p 和 q，则当前节点就是 LCA如果只有一侧有非空结果，说明 LCA 在那一侧递归函数定义：TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)返回：以 root 为根的子树中包含 p 或 q 的节点，如果都不包含则返回 null。详细步骤递归终止条件：如果 root 为 null，返回 null如果 root 等于 p 或 q，返回 root（因为找到了目标节点）递归左右子树：left = LCA(root.left, p, q)right = LCA(root.right, p, q)判断情况：如果 left 和 right 都不为空 → root 是 LCA如果 left 不为空，right 为空 → 返回 left如果 right 不为空，left 为空 → 返回 right如果都为空 → 返回 null示例推演以二叉树 [3,5,1,6,2,0,8,null,null,7,4] 为例，找节点 5 和 1 的 LCA： 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4递归过程：LCA(3,5,1)：左子树：LCA(5,5,1) → 找到5，返回5右子树：LCA(1,5,1) → 找到1，返回1左右都不为空 → 返回3（LCA）找节点 5 和 4 的 LCA：LCA(3,5,4)：左子树：LCA(5,5,4)：左子树：LCA(6,5,4) → 不包含，返回null右子树：LCA(2,5,4)：左子树：LCA(7,5,4) → null右子树：LCA(4,5,4) → 找到4，返回4左右：null和4 → 返回4当前节点5等于p → 返回5左右：null和4 → 但当前节点是5，所以返回5右子树：LCA(1,5,4) → 不包含，返回null左右：5和null → 返回5（LCA）

LeetCode 114. 二叉树展开为链表 [Hot 100]
type: item
date: 2025-09-24T11:37:00+08:00
description: 114. 二叉树展开为链表已解答中等给你二叉树的根结点 root ，请你将它展开为一个单链表：展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。示例 1：输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]示例 2：输入：root = [] 输出：[]示例 3：输入：root = [0] 输出：[0]/** * 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 { TreeNode pre = null; public void flatten(TreeNode root) { if (root == null) return; flatten(root.right); flatten(root.left); root.right=pre; root.left=null; pre=root; } }1. 遍历顺序：右 → 左 → 根假设我们有二叉树： 1 / \ 2 5 / \ \ 3 4 6先序遍历：1 → 2 → 3 → 4 → 5 → 6我们要让展开后的链表是这个顺序。2. 递归处理过程我们定义 prev 为全局变量（或通过参数传递），表示当前已经处理好的链表的最后一个节点。递归函数 flatten(TreeNode root) 的作用：将以 root 为根的子树展开成链表，并更新 prev。处理顺序：先递归处理右子树再递归处理左子树最后处理根节点3. 为什么是右 → 左 → 根？因为我们要让链表顺序是先序遍历（根 → 左 → 右），但递归是"归来"时处理连接，所以要从后往前构建链表：先处理最右边的节点（6），它将是链表的末尾然后处理左边的节点（4, 3, 2）最后处理根节点（1）这样在连接时，prev 始终指向当前已经构建好的链表的头部（实际上是已经构建部分的最后一个节点）。