本文解析 leetcode「二叉树中的伪回文路径」题目中因路径数组深拷贝导致的 javascript 堆内存溢出问题，提出基于状态对象复用与浅层克隆的高效递归方案，并给出空间复杂度优化的关键实践。
本文解析 leetcode「二叉树中的伪回文路径」题目中因路径数组深拷贝导致的 javascript 堆内存溢出问题，提出基于状态对象复用与浅层克隆的高效递归方案，并给出空间复杂度优化的关键实践。
在解决 LeetCode 1457. 二叉树中的伪回文路径 时，初版代码虽逻辑正确，却在大规模输入下触发 FATAL ERROR: MarkCompactCollector: young object promotion failed ——本质是 V8 引擎堆内存耗尽。根本原因在于：每次递归调用都通过 [...parents] 对路径数组进行全量浅拷贝，而路径长度随树深度线性增长，递归分支数呈指数级扩张，导致内存占用爆炸式上升（O(N × H) 空间，H 为树高）。
? 问题定位：低效的路径表示方式
原实现中：
var dfs = (node, parents) => {
parents.push(node.val); // 修改原数组
if (!node.left && !node.right) {
if (isPalindromic(parents)) total++;
return;
}
if (node.left) dfs(node.left, [...parents]); // ❌ 每次创建新数组（深拷贝开销大）
if (node.right) dfs(node.right, [...parents]);
};
-
parents是数组，[...parents]在每次分支前生成新副本； - 对于深度为
H的满二叉树，叶节点数约2^H，每条路径平均长H，总内存 ≈2^H × H，极易 OOM。
✅ 正确解法：状态对象 + 结构共享 + 按需克隆
优化核心思想：用固定大小的对象（而非动态数组）记录数字频次，并仅在分支时克隆轻量级频次映射对象。
var pseudoPalindromicPaths = function(root) {
let total = 0;
// 频次表：仅支持 1–9，固定 9 个属性，内存恒定 O(1)
const initCount = { "1": 0, "2": 0, "3": 0, "4": 0, "5": 0, "6": 0, "7": 0, "8": 0, "9": 0 };
const dfs = (node, count) => {
count[node.val]++; // 就地更新频次（无数组扩容开销）
// 到达叶子节点：校验是否可构成伪回文（至多一个数字出现奇数次）
if (!node.left && !node.right) {
let oddCount = 0;
for (const freq of Object.values(count)) {
if (freq % 2 === 1 && ++oddCount > 1) break;
}
if (oddCount <h3>⚙️ 关键优化点说明</h3>
| 维度 | 原方案 | 优化后 |
|---|---|---|
| 空间模型 |
O(H) 数组 × O(2^H) 分支 → O(H·2^H)
|
O(1) 频次对象 × O(2^H) 分支 → O(2^H)（常数因子极小） |
| 克隆开销 | 每次 ...arr 复制 H 个整数 |
每次 {...count} 复制 9 个整数（严格 O(1)） |
| 路径重建 | 需在叶节点重新统计频次（O(H)） | 频次实时维护，校验仅 O(1)（固定 9 次迭代） |
? 进阶提示：还可进一步用位运算优化（如
mask ^= (1 记录奇偶性），将频次对象压缩为单个整数，使克隆开销降至极致（<code>mask传值即可，无需{...}），但当前对象方案已足够通过所有测试用例且语义清晰。
✅ 总结
避免递归中高频深拷贝是 JavaScript 树类题目的通用避坑原则。本例启示我们：
- 优先使用不可变、定长的状态表示（如频次对象/位掩码），替代易膨胀的路径数组；
- 克隆粒度越小越好：从“整条路径”降级到“9 个计数器”，空间复杂度实现质的飞跃；
- Leaf-check 逻辑内联：避免额外遍历，让状态维护与校验一体化。
该优化将最坏情况内存占用从指数级降至线性分支数级别，彻底解决堆溢出问题，同时保持代码可读性与工程健壮性。
