## 问题描述

给定一个由连续正整数组成的数组N和一个目标整数M，计算使用以下两种方式构建M的方法总数：

1. 仅使用数组N中的元素（每个元素可以重复使用）
2. 使用一个不在N中的元素x（x必须小于N中的最小元素），再加上N中的元素（同样可以重复使用）



## 示例分析

**示例1**：
```
输入：N = [1, 2], M = 4
输出：4
解释：
方法1：1+1+1+1
方法2：1+1+2
方法3：2+2
方法4：使用x=0（如果允许），加上1+1+2（但通常x最小为1）
```

**示例2**：
```
输入：N = [2, 5], M = 4
输出：1
解释：
方法1：2+2=4
（不能使用x=1，因为1+3=4但3不在N中）
```

## 算法思路

这个问题可以分解为两个子问题：

1. **完全背包问题**：计算仅使用N中元素组成M的方法数
2. **扩展背包问题**：计算使用一个额外元素x（x < min(N)）加上N中元素组成M的方法数

### 动态规划解法

我们使用动态规划来解决这个组合问题：

```java
public static int countAssemblyMethods(int[] N, int M) {
    // 情况1：仅使用N中的元素（可重复使用）
    int ways1 = countUnboundedSubsetSum(N, M);
    
    // 情况2：使用一个不在N中的元素x（x < N[0]），再加上N中的元素
    int ways2 = 0;
    if (N.length > 0 && N[0] > 1) {
        for (int x = 1; x < N[0]; x++) {
            if (M > x) {
                ways2 += countUnboundedSubsetSum(N, M - x);
            } else if (M == x) {
                ways2 += 1;  // 单独使用x的情况
            }
        }
    }
    
    return ways1 + ways2;
}
```

### 完全背包实现

```java
private static int countUnboundedSubsetSum(int[] nums, int sum) {
    int[] dp = new int[sum + 1];
    dp[0] = 1;  // 和为0只有一种方法：不选任何元素
    
    for (int num : nums) {
        for (int i = num; i <= sum; i++) {
            dp[i] += dp[i - num];
        }
    }
    
    return dp[sum];
}
```

### 完整代码
```java
import java.util.Scanner;

public class ArrayAssembly {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入数组N
        String[] nStr = scanner.nextLine().split(" ");
        int[] N = new int[nStr.length];
        for (int i = 0; i < nStr.length; i++) {
            N[i] = Integer.parseInt(nStr[i]);
        }
        
        // 读取整数M
        int M = Integer.parseInt(scanner.nextLine());
        
        // 计算并输出组装方法数量
        System.out.println(countAssemblyMethods(N, M));
        
        scanner.close();
    }
    
    public static int countAssemblyMethods(int[] N, int M) {
        // 情况1：仅使用N中的元素（可重复使用）
        int ways1 = countUnboundedSubsetSum(N, M);
        
        // 情况2：使用一个不在N中的元素x（x < N[0]），再加上N中的元素（可重复）
        int ways2 = 0;
        if (N.length > 0 && N[0] > 1) {
            for (int x = 1; x < N[0]; x++) {
                if (M > x) {
                    ways2 += countUnboundedSubsetSum(N, M - x);
                } else if (M == x) {
                    ways2 += 1;  // 单独使用x的情况
                }
            }
        }
        
        return ways1 + ways2;
    }
    
    // 允许重复使用元素的子集和计算（完全背包）
    private static int countUnboundedSubsetSum(int[] nums, int sum) {
        int[] dp = new int[sum + 1];
        dp[0] = 1;
        
        for (int num : nums) {
            for (int i = num; i <= sum; i++) {
                dp[i] += dp[i - num];
            }
        }
        
        return dp[sum];
    }
}
```

## 复杂度分析

- **时间复杂度**：O(M×n)，其中n是数组N的长度
- **空间复杂度**：O(M)，用于存储DP数组

## 边界情况处理

1. **空数组N**：只能使用x=M（如果允许）
2. **M=0**：只有一种方法（不选任何元素）
3. **N中包含1**：x的取值会减少（因为x必须小于min(N)）

## 实际应用

这类组合问题在实际中有广泛应用，例如：

1. 货币找零问题
2. 资源分配问题
3. 密码学中的组合加密
4. 游戏开发中的道具合成系统

## 总结

通过将问题分解为两个子问题，并运用动态规划技术，我们能够高效地计算出所有可能的组合方式。关键在于：

1. 正确识别问题类型（完全背包问题）
2. 处理好边界条件
3. 将复杂问题分解为更小的子问题

这种解法不仅适用于本问题，其思路也可以推广到其他类似的组合问题中。

---

**思考题**：如果题目改为不允许重复使用N中的元素，算法应该如何修改？欢迎在评论区分享你的解决方案！

组合数组元素构建目标值的算法解析

# ZGC垃圾收集器：原理、演进与优化实践

ZGC（Z Garbage Collector）是Java平台上一款革命性的低延迟垃圾收集器，由Oracle开发并逐步成为现代Java应用处理大内存堆和低延迟需求的首选解决方案。本文将全面剖析ZGC的核心原理、技术演进、关键特性以及实际调优策略，帮助开发者深入理解这一先进的垃圾收集技术。

## ZGC概述与发展历程

ZGC最初作为实验性功能在JDK 11中引入（JEP 333），经过多个版本的迭代优化，到JDK 15时被宣布为生产就绪（Production Ready）。其设计目标是**在任意堆内存大小下都能将垃圾收集停顿时间控制在10毫秒以内**，同时尽可能减少对吞吐量的影响。



ZGC的发展历程体现了Java平台对低延迟垃圾收集的持续追求：
- **JDK 11**：首次引入，支持最大4TB堆内存
- **JDK 15**：提升至16TB堆内存支持，正式成为生产级功能
- **JDK 21**：引入分代收集模式（JEP 439），显著提升效率
- **JDK 23**：将分代模式设为默认（JEP 474），标志技术成熟

ZGC的名称中的"Z"并非缩写，而是向ZFS文件系统致敬，象征着这是一款**革命性的、跨时代的产品**。与传统的垃圾收集器不同，ZGC从设计之初就专注于解决大内存堆下的低延迟问题，采用了多项创新技术实现这一目标。

## 核心架构与内存模型

### 基于Region的堆布局

ZGC采用**基于Region的堆内存布局**，与G1收集器类似，但具有更高的动态性。在x64平台下，ZGC将堆划分为三类不同大小的Region：

1. **小型Region(Small Region)**：固定2MB容量，存放小于256KB的小对象
2. **中型Region(Medium Region)**：固定32MB容量，存放256KB-4MB的中等对象
3. **大型Region(Large Region)**：容量动态可变（2MB的整数倍），每个Region只存放一个大对象（≥4MB）

这种设计使ZGC能够**根据对象大小智能分配内存**，既提高了小对象的分配效率，又避免了大对象造成的内存碎片。大型Region不会被重分配（因为复制大对象代价高昂），而中小型Region则可以根据回收策略动态创建和销毁。

### 分代与非分代模式

在JDK 21之前，ZGC采用**不分代**的全堆收集策略，每次GC都需要扫描所有对象。基于"弱分代假说"（绝大多数对象朝生暮死）和"强分代假说"（老年对象难以死亡），JDK 21引入了分代ZGC（Generational ZGC）。

分代ZGC将堆划分为**逻辑上的新生代和老年代**（物理上不要求连续），并采用不同的回收策略：
- **Minor GC**：只回收新生代，速度快频率高
- **Major GC**：回收整个堆，包括新生代和老年代，速度慢频率低

分代模式通过更频繁地收集新生代对象，显著提高了资源利用率和性能。测试表明，分代ZGC不仅能保持亚毫秒级延迟，**在很多情况下比非分代模式使用更少内存且吞吐量损失更小**。

## 关键技术实现

### 染色指针（Colored Pointers）

染色指针是ZGC最具标志性的技术创新，它将**GC元数据直接存储在对象指针中**，而非传统GC那样存储在对象头里。在64位Linux系统中，ZGC利用指针中高18位不能用于寻址的特性，使用其中4位作为标志位：

```
18位：预留给以后使用；
1位：Finalizable标识（与并发引用处理相关）；
1位：Remapped标识（对象是否指向重分配集）；
1位：Marked1标识；
1位：Marked0标识（用于辅助GC）；
42位：对象地址（支持4TB内存）
```

染色指针技术带来了三大核心优势：
1. **快速释放内存**：Region中存活对象被移走后可立即重用，不必等待所有引用更新
2. **减少内存屏障**：只需使用读屏障，大幅降低GC开销
3. **可扩展的存储结构**：为未来功能扩展预留空间

在分代ZGC中，染色指针布局进一步优化，**将元数据放在指针低位，地址放在高位**，使得通过单个移位指令（x64架构）就能检查指针状态并移除元数据。

### 并发处理与内存屏障

ZGC是一款**完全并发**的收集器，所有繁重工作都与应用程序线程并行执行。为实现这点，ZGC采用了创新的屏障技术：

1. **读屏障(Load Barrier)**：类似于AOP的前置通知，当读取处于重分配集的对象时，屏障会拦截并转发到新对象，同时更新引用值，这种"自愈"能力确保应用代码总是持有有效指针

2. **存储屏障(Store Barrier)**：分代ZGC新增的屏障，负责无色指针到有色指针的转换、维护记忆集和标记存活对象

分代ZGC通过**快慢路径分离**优化屏障性能：快路径由JIT实现并直接插入编译代码；慢路径用C++实现处理复杂情况；还引入中间路径缓冲存储操作，只有当缓冲区满时才进入慢路径，大幅减少开销。

### 记忆集与SATB

分代ZGC采用**双重缓冲记忆集**，由两个bitmap实现（非传统卡表）：
- 一个bitmap供用户线程修改（写屏障中）
- 一个只读bitmap供GC使用

这种设计消除了清除bitmap时的等待，也不需要额外内存屏障。对于并发标记期间引用变化导致的漏标问题，ZGC使用**SATB(Snapshot-At-The-Beginning)**算法解决，与G1收集器类似。

## ZGC的运作过程

ZGC的完整收集周期可分为四个主要阶段，**其中仅包含三个短暂的STW停顿**：

1. **并发标记(Concurrent Mark)**：
   - 遍历对象图做可达性分析
   - 更新染色指针中的Marked0/Marked1标志位
   - 标记在指针而非对象上进行，提高效率

2. **并发预备重分配(Concurrent Prepare for Relocate)**：
   - 统计确定需要清理的Region，组成重分配集(Relocation Set)
   - 类似G1的回收集(Collection Set)，但选择策略不同

3. **并发重分配(Concurrent Relocate)**：
   - 核心工作阶段，将存活对象移动到新Region
   - 通过转发表(Forward Table)处理旧引用

4. **并发重映射(Concurrent Remap)**：
   - 修正所有指向重分配集中对象的引用
   - 可与下一轮标记合并进行，减少开销

分代ZGC的回收过程更精细，分为Minor GC和Major GC两种模式。Minor GC时初始标记的根集合包含：
- GC roots中指向新生代的引用
- 老年代记忆集(remembered sets)

## 性能调优与实践

### 关键配置参数

ZGC设计哲学是**简化调优**，大多数情况下只需设置堆大小即可：

| 参数 | 作用 | 默认值 | 优化建议 |
|------|------|--------|----------|
| -Xms/-Xmx | 堆最小/最大大小 | 物理内存1/4 | 设为相同值避免堆震荡 |
| -XX:+UseZGC | 启用ZGC | 关闭 | 低延迟场景必选 |
| -XX:+ZGenerational | 启用分代模式(JDK21+) | JDK23默认开启 | 多数情况建议开启 |
| -XX:ConcGCThreads | 并发GC线程数 | CPU核心数12.5% | 内存压力大时可适当增加 |
| -XX:ZCollectionInterval | 最小回收间隔 | 10秒 | 突发分配场景可延长 |
| -XX:+UseLargePages | 启用大页内存 | 关闭 | 提升吞吐量和降低延迟 |
| -XX:+UseNUMA | NUMA支持 | 开启 | 多插槽服务器保持开启 |
| -XX:+ZUncommit | 返还闲置内存给OS | 开启 | 容器环境建议开启 |

### 触发机制与停顿分析

ZGC的触发机制主要有三类：
1. **基于分配速率**：当内存分配速度超过回收速度时触发
2. **基于时间间隔**：-XX:ZCollectionInterval控制
3. **主动触发**：-XX:+ZProactive启用预测性回收

常见的停顿原因包括：
- **GC过程STW**：初始标记(Pause Mark Start)、再标记(Pause Mark End)、初始转移(Pause Relocate Start)
- **非GC停顿**：内存分配阻塞(Allocation Stall)、安全点(Safepoint)、线程/内存Dump

### 优化建议

1. **堆大小设置**：
   - 生产环境建议-Xms和-Xmx设为相同值
   - 堆大小应能容纳活动对象集并有足够缓冲空间
   - 通常建议堆大小为活动对象集的3-4倍

2. **大页内存配置**：
   ```bash
   # 配置Linux大页(需root)
   echo 9216 > /proc/sys/vm/nr_hugepages
   # 启用ZGC大页支持
   -XX:+UseLargePages
   ```
   大页(2MB)能减少TLB缺失，提升性能

3. **NUMA优化**：
   - 多插槽服务器建议保持-XX:+UseNUMA开启
   - 单NUMA节点系统会自动禁用

4. **监控与日志**：
   ```bash
   -Xlog:gc*=info:file=gc.log:time,tags:filecount=10,filesize=100m
   ```
   分析GC日志关注：
   - 停顿时间分布
   - 并发阶段耗时
   - 内存回收效率

## 与传统GC的对比

| 特性 | ZGC | G1 | CMS | Parallel |
|------|-----|----|-----|----------|
| 设计目标 | 大堆低延迟 | 平衡延迟/吞吐 | 老年代低延迟 | 高吞吐量 |
| 最大暂停目标 | <10ms | 200ms左右 | 不可预测 | 无保证 |
| 堆大小支持 | 16TB+ | 4TB-32TB | 一般<4TB | 一般<4TB |
| 分代支持 | JDK21+支持 | 支持 | 支持 | 支持 |
| 压缩算法 | 并发压缩 | 部分压缩 | 不压缩 | 全压缩 |
| 内存屏障 | 读屏障+存储屏障 | 写屏障 | 写屏障 | 无 |
| 适用场景 | 大内存低延迟 | 平衡型应用 | 老年代低延迟 | 批处理作业 |

## 未来发展与挑战

ZGC仍在持续演进，未来可能的发展方向包括：
1. **更大堆支持**：当前16TB+的限制可能进一步扩展
2. **元空间优化**：减少Metaspace的GC影响
3. **云原生适配**：更好适应容器环境的内存弹性
4. **AI驱动的自适应**：根据工作负载自动优化参数

实际使用中的挑战主要有：
- 分代模式下的记忆集维护开销
- 极端情况下Allocation Stall问题
- 与JNI代码的交互成本

## 总结

ZGC代表了Java垃圾收集技术的最前沿，通过染色指针、并发处理和分代收集等创新技术，实现了大内存堆下的亚毫秒级停顿。从JDK11到JDK23的演进过程中，ZGC逐渐成熟并成为处理现代Java应用低延迟需求的优选方案。

对于开发者而言，理解ZGC的核心原理和调优方法，能够帮助我们在以下场景中获得最佳性能：
- 大数据处理框架（如Spark、Flink）的内存管理
- 金融交易系统等低延迟应用
- 云原生环境中的Java服务
- 游戏服务器等实时系统

随着Java生态的持续发展，ZGC很可能会成为新一代Java应用的默认垃圾收集器，其设计理念和技术实现值得每一位Java开发者深入学习和掌握。

ZGC垃圾收集器：原理、演进与优化实践

# 摩尔投票算法（Moore's Voting Algorithm）Java实现

摩尔投票算法是一种高效的算法，用于在数组中寻找出现次数超过一半或特定比例的元素。以下是摩尔投票算法的Java实现及其详细解析。

## 基础版：寻找出现次数超过一半的元素



```java
public class MajorityElement {
    public static int findMajorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (candidate == num) {
                count++;
            } else {
                count--;
            }
        }
        
        // 验证候选元素是否确实超过半数
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        
        return count > nums.length / 2 ? candidate : -1; // 返回-1表示没有多数元素
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 3, 3, 4, 3, 5, 3};
        int majorityElement = findMajorityElement(nums);
        System.out.println("出现次数超过一半的元素是：" + majorityElement);
    }
}
```

### 算法解析

1. **初始化**：设置候选元素`candidate`和计数器`count`为0
2. **遍历数组**：
   - 当`count`为0时，将当前元素设为候选元素
   - 当前元素等于候选元素时，`count`加1
   - 当前元素不等于候选元素时，`count`减1
3. **验证阶段**：再次遍历数组，统计候选元素的实际出现次数，确认是否超过半数

该算法时间复杂度为O(n)，空间复杂度为O(1)

## 进阶版：寻找出现次数超过n/3的元素

```java
import java.util.ArrayList;
import java.util.List;

public class MajorityElementII {
    public static List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;
        
        // 第一轮遍历找出两个候选元素
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        // 第二轮遍历验证候选元素
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }
        
        if (count1 > nums.length / 3) {
            result.add(candidate1);
        }
        if (count2 > nums.length / 3 && candidate1 != candidate2) {
            result.add(candidate2);
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 3, 3, 2, 2, 2};
        List<Integer> majorityElements = majorityElement(nums);
        System.out.println("出现次数超过n/3的元素是：" + majorityElements);
    }
}
```

### 算法解析

1. **初始化**：设置两个候选元素`candidate1`、`candidate2`和对应的计数器`count1`、`count2`
2. **遍历数组**：
   - 当前元素等于任一候选元素时，对应计数器加1
   - 当任一计数器为0时，将当前元素设为对应候选元素
   - 否则，两个计数器都减1
3. **验证阶段**：统计两个候选元素的实际出现次数，确认是否超过n/3

该算法同样保持O(n)时间复杂度和O(1)空间复杂度

## 算法特点

1. **高效性**：只需1-2次线性遍历，无需额外数据结构
2. **空间优化**：仅使用常数空间
3. **应用场景**：
   - 选举系统统计
   - 数据分析中的频繁项挖掘
   - 流数据处理

## 注意事项

1. 基础版算法假设数组中一定存在多数元素，否则需要验证阶段
2. 进阶版最多可能返回2个结果（因为超过n/3的元素最多两个）
3. 对于流式数据，算法同样适用，因为只需一次遍历

摩尔投票算法因其简洁高效的特点，成为解决多数元素问题的首选方案。

摩尔投票算法

# JDK 17新特性全面解析

JDK 17作为Java的长期支持(LTS)版本，于2021年9月发布，带来了多项重要更新和改进。以下是JDK 17的主要新特性分类整理：

## 一、语言特性增强

### 1. 模式匹配(Pattern Matching)
JDK 17对模式匹配进行了多项增强，使代码更加简洁易读：



- **instanceof模式匹配**：简化类型检查和转换
```java
// 旧写法
if (obj instanceof String) {
    String str = (String) obj;
    System.out.println(str.toUpperCase());
}

// 新写法
if (obj instanceof String str) {
    System.out.println(str.toUpperCase());
}
```

- **switch表达式增强**：支持箭头语法和模式匹配
```java
switch (day) {
    case MONDAY, FRIDAY -> System.out.println("Weekday");
    case SATURDAY, SUNDAY -> System.out.println("Weekend");
    default -> throw new IllegalArgumentException("Invalid day");
}
```

- **记录类型(Record)的模式匹配**：简化数据类的处理
```java
record Point(int x, int y) {}

if (obj instanceof Point p) {
    System.out.println("Point(" + p.x() + ", " + p.y() + ")");
}
```


### 2. 密封类(Sealed Classes)
密封类允许开发者限制哪些类可以继承或实现它们，提供更严格的访问控制：

```java
public sealed class Shape permits Circle, Rectangle, Square {
    public abstract double area();
}

public final class Circle extends Shape { /* ... */ }
public final class Rectangle extends Shape { /* ... */ }
public final class Square extends Shape { /* ... */ }
```

密封类增强了代码安全性，促进更好的代码组织结构，并支持模式匹配。

### 3. 文本块(Text Blocks)
文本块简化了多行字符串的编写，特别适合JSON、HTML、SQL等内容：

```java
// 旧写法
String html = "<html>\n" +
              " <body>\n" +
              " <p>Hello, world</p>\n" +
              " </body>\n" +
              "</html>";

// 新写法
String html = """
              <html>
               <body>
               <p>Hello, world</p>
               </body>
              </html>
              """;
```


## 二、API改进与新增功能

### 1. 增强的伪随机数生成器(JEP 356)
JDK 17为伪随机数生成器(PRNG)提供了新的接口和实现：

- 新接口`RandomGenerator`统一了所有PRNG的API
- 新类`RandomGeneratorFactory`用于定位和构造PRNG实例
- 支持可跳转的PRNG和LXM算法

```java
RandomGenerator generator = RandomGeneratorFactory.of("L128X128MixRandom").create();
IntStream ints = generator.ints(50, 0, 10);
```


### 2. NullPointerException增强
JDK 17提供了更详细的空指针异常信息，帮助开发者快速定位问题源头：

```java
public static void main(String[] args) {
    try {
        var arr = List.of(null);
        String str = (String)arr.get(0);
        str.length();
    } catch (Exception e) {
        e.printStackTrace(); // 会显示更详细的NPE信息
    }
}
```


### 3. 记录类型(Records)
记录类型提供了一种简洁的方式来定义不可变的数据聚合：

```java
public record StudentRecord(Long stuId, String stuName, int stuAge, 
                          String stuGender, String stuEmail) {
    public StudentRecord {
        System.out.println("构造函数");
    }
}
```


## 三、JVM与性能改进

### 1. 垃圾收集器增强
JDK 17对垃圾收集器进行了多项改进：

- **ZGC**：低延迟垃圾收集器，支持16TB堆内存，停顿时间<10ms
```bash
java -XX:+UseZGC -jar myapp.jar
```

- **Shenandoah GC**：低停顿时间垃圾收集器
```bash
java -XX:+UseShenandoahGC -jar myapp.jar
```

- **G1 GC**：默认垃圾收集器，改进内存分配和并行处理


### 2. 强封装JDK内部API
JDK 17加强了内部API的封装，老版本直接访问内部类的方式不再可行，需要通过服务提供者机制访问。

## 四、其他重要特性

### 1. 外部函数和内存API(JEP 412)
提供与本地代码(如C/C++)交互的标准方式，支持操作非托管内存和调用C语言函数。

### 2. Vector API(第二次孵化)
支持SIMD指令集，进行高性能并行计算，优化向量化操作。

### 3. Unix域套接字通道(JEP 380)
支持同一主机上进程间的高效本地通信。

### 4. 移除功能
- 删除Applet API(JEP 398)
- 删除远程方法调用激活机制(JEP 407)
- 删除实验性的AOT和JIT编译器(JEP 410)
- 删除弃用的安全管理器(JEP 411)


## 五、升级与迁移建议

JDK 17是继Java 8以来最重要的LTS版本，Spring 6.x和Spring Boot 3.x最低支持Java 17。根据统计，Java 17的使用率在一年内增长了430%，已有超过9%的应用程序在生产中使用。

升级到JDK 17可以获得：
1. 更简洁的现代Java语法
2. 更好的性能(特别是垃圾收集)
3. 增强的安全性
4. 长期支持(直到2029年)

对于新项目，建议直接采用JDK 17；对于现有项目，可根据实际情况制定迁移计划。

## 总结对比表

| 特性类别 | 主要改进 | 相关JEP | 重要性 |
|---------|---------|--------|--------|
| 语言特性 | 模式匹配、密封类、文本块 | JEP 406, 409 | ⭐⭐⭐⭐⭐ |
| API改进 | 伪随机数、NPE增强、Records | JEP 356, 395 | ⭐⭐⭐⭐ |
| JVM性能 | ZGC/Shenandoah增强 | JEP 376, 387 | ⭐⭐⭐⭐ |
| 本地交互 | 外部函数和内存API | JEP 412 | ⭐⭐⭐ |
| 移除功能 | Applet、RMI激活等 | JEP 398, 407 | ⭐⭐ |

JDK 17的新特性使Java语言更现代化，提高了开发效率和运行时性能，是企业应用升级的理想选择。

JDK 17新特性全面解析

二叉树作为计算机科学中最基础且重要的数据结构之一，其遍历操作是算法学习的关键内容。本文将系统介绍二叉树的三种经典遍历方式——前序遍历、中序遍历和后序遍历，从基本概念到递归与非递归实现，从理论分析到实际应用，帮助读者全面掌握二叉树遍历技术。

## 一、二叉树遍历的基本概念

### 1. 遍历方式的定义与命名



二叉树遍历是指按照某种顺序访问树中所有节点且每个节点仅访问一次的过程。三种遍历方式的命名来源于**根节点的访问时机**：

- **前序遍历(Preorder Traversal)**：按照"根节点→左子树→右子树"的顺序访问
- **中序遍历(Inorder Traversal)**：按照"左子树→根节点→右子树"的顺序访问
- **后序遍历(Postorder Traversal)**：按照"左子树→右子树→根节点"的顺序访问

这三种遍历方式都属于深度优先搜索(DFS)策略，与广度优先搜索(BFS)的层序遍历形成对比。

### 2. 遍历顺序的直观理解

通过形象比喻可以快速记忆三种遍历方式：

- **前序遍历**：如同一个人从根节点出发，沿着树的外围"跑一圈"，经过节点的顺序就是前序序列。每次遇到节点时立即访问，且不重复记录已访问过的节点。
  
- **中序遍历**：将每个节点垂直"投影"到一条水平线上，从左到右的顺序即为中序序列。这种投影方式自然体现了"左→根→右"的访问顺序。

- **后序遍历**：类似于剪枝过程，只有当一个节点的所有子节点都被"剪掉"(访问)后，才访问该节点本身。

*示例*：对于二叉树：
```
    A
   / \
  B   C
 / \   \
D   E   F
```
其遍历结果为：
- 前序：A B D E C F
- 中序：D B E A C F
- 后序：D E B F C A

## 二、递归实现详解

递归实现是三种遍历方式最直观的表达，直接反映了遍历的定义。

### 1. 前序遍历递归实现

```java
void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " "); // 访问根节点
    preOrder(root.left);              // 递归左子树
    preOrder(root.right);             // 递归右子树
}
```

**执行过程分析**：
1. 访问根节点A，打印A
2. 递归处理A的左子树(B为根)
   - 访问B，打印B
   - 递归处理B的左子树(D为根)
     - 访问D，打印D
     - D的左右子树为空，返回
   - 递归处理B的右子树(E为根)
     - 访问E，打印E
     - E的左右子树为空，返回
3. 递归处理A的右子树(C为根)
   - 访问C，打印C
   - C的左子树为空
   - 递归处理C的右子树(F为根)
     - 访问F，打印F
     - F的左右子树为空，返回

### 2. 中序遍历递归实现

```java
void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);               // 递归左子树
    System.out.print(root.val + " "); // 访问根节点
    inOrder(root.right);              // 递归右子树
}
```

**执行特点**：
- 优先递归到最左节点开始访问
- 对于每个子树，总是先处理完所有左节点再处理根节点
- 适合产生有序输出(对二叉搜索树)

### 3. 后序遍历递归实现

```java
void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);             // 递归左子树
    postOrder(root.right);             // 递归右子树
    System.out.print(root.val + " ");  // 访问根节点
}
```

**应用场景**：
- 需要先处理子节点再处理父节点的场景
- 计算表达式树的值
- 释放二叉树内存

## 三、非递归实现详解

虽然递归实现简洁，但非递归实现(迭代法)更高效且不易栈溢出。

### 1. 前序遍历非递归实现

**算法思路**：
1. 使用栈模拟递归调用栈
2. 先将根节点入栈
3. 循环执行：
   - 弹出栈顶节点并访问
   - 将其右子节点入栈(如果存在)
   - 将其左子节点入栈(如果存在)
   
```java
void preOrderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}
```

**关键点**：由于栈的LIFO特性，要先压入右子节点再压入左子节点，才能保证访问顺序为根→左→右。

### 2. 中序遍历非递归实现

**算法思路**：
1. 使用栈和当前节点指针
2. 循环执行：
   - 将当前节点及其所有左子节点依次入栈
   - 弹出栈顶节点访问
   - 转向右子树处理

```java
void inOrderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        System.out.print(curr.val + " ");
        curr = curr.right;
    }
}
```

**难点解析**：需要理解内层while循环将所有左子节点压栈的过程，以及访问后转向右子树的处理逻辑。

### 3. 后序遍历非递归实现

后序遍历的非递归实现最为复杂，需要记录前一个访问的节点。

**算法思路**：
1. 使用栈和两个指针(current和lastVisited)
2. 先将根节点及其所有左子节点入栈
3. 查看栈顶节点：
   - 如果右子树存在且未被访问，转向右子树
   - 否则，访问该节点并标记

```java
void postOrderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root, lastVisited = null;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.peek();
        if (curr.right == null || curr.right == lastVisited) {
            System.out.print(curr.val + " ");
            lastVisited = stack.pop();
            curr = null;
        } else {
            curr = curr.right;
        }
    }
}
```

**核心技巧**：通过`lastVisited`指针判断右子树是否已被处理，避免重复访问。

## 四、遍历序列与二叉树重建

### 1. 遍历序列还原二叉树

**已知前序和中序序列**可以唯一确定二叉树：
1. 前序序列第一个元素为根节点
2. 在中序序列中找到该根节点，左边为左子树，右边为右子树
3. 递归处理左右子树

*示例*：
- 前序：A B D E C F
- 中序：D B E A C F

重建步骤：
1. A为根节点
2. 中序中A左边(D B E)为左子树，右边(C F)为右子树
3. 前序中B D E为左子树部分，C F为右子树部分
4. 对左子树：前序B D E，中序D B E → B为根，D为左，E为右
5. 对右子树：前序C F，中序C F → C为根，F为右

**已知中序和后序序列**同样可以唯一确定二叉树：
1. 后序序列最后一个元素为根节点
2. 在中序序列中找到该根节点划分左右子树
3. 递归处理

**重要限制**：仅凭前序和后序序列**不能**唯一确定二叉树。

### 2. 应用案例

1. **表达式树**：
   - 中序序列：中缀表达式
   - 后序序列：后缀表达式(逆波兰表示法)
   - 前序序列：前缀表达式(波兰表示法)

2. **目录结构显示**：
   - 前序遍历可显示目录树结构
   - 后序遍历可计算目录大小

## 五、三种遍历的对比与应用

### 1. 特性对比

| **特性**        | **前序遍历**            | **中序遍历**              | **后序遍历**            |
|----------------|------------------------|--------------------------|------------------------|
| 访问顺序         | 根→左→右                | 左→根→右                  | 左→右→根                |
| 递归实现复杂度     | O(n)                   | O(n)                     | O(n)                   |
| 非递归实现难度     | 较简单                  | 中等                      | 较复杂                  |
| 典型应用         | 复制二叉树、前缀表达式    | 二叉搜索树有序输出、中缀表达式 | 删除二叉树、后缀表达式    |
| 序列唯一性       | 不能单独确定树结构        | 需配合其他序列             | 不能单独确定树结构        |

### 2. 应用场景选择建议

1. **选择前序遍历当**：
   - 需要先访问父节点再访问子节点
   - 需要复制二叉树结构
   - 生成目录结构显示

2. **选择中序遍历当**：
   - 处理二叉搜索树(BST)时需有序输出
   - 需要中缀表达式表示
   - 需要按从小到大顺序处理节点

3. **选择后序遍历当**：
   - 需要先处理子节点再处理父节点
   - 释放树结构内存
   - 计算子树信息(如节点数、高度)

## 六、进阶主题与优化

### 1. Morris遍历算法

一种空间复杂度为O(1)的遍历算法，通过利用叶子节点的空指针实现：
- 不需要使用栈
- 通过临时修改树结构实现遍历
- 遍历完成后恢复树结构

### 2. 多线程遍历

对于大规模二叉树：
- 可对左右子树并行遍历
- 需要线程安全的数据结构
- 特别适合后序遍历实现

### 3. 遍历可视化工具

使用Graphviz等工具生成遍历过程动画：
- 红色表示当前访问节点
- 灰色表示已访问节点
- 黑色表示未访问节点

## 七、常见问题与解决方案

1. **栈溢出问题**：
   - 对深度很大的树，递归实现可能导致栈溢出
   - 解决方案：改用非递归实现或增加栈空间

2. **遍历结果不一致**：
   - 检查二叉树结构是否被意外修改
   - 验证遍历实现的正确性

3. **性能优化**：
   - 对频繁遍历操作，可缓存遍历结果
   - 考虑使用迭代器模式实现延迟遍历

理解并掌握二叉树的三种基本遍历方式，是学习更复杂树形结构和算法的基础。通过递归与非递归实现的对比，可以深入理解计算机如何处理递归逻辑。实际应用中，根据具体需求选择合适的遍历方式，能够大大提高算法效率和代码可维护性。