二叉树伪回文路径求解遇堆内存溢出问题及优化咨询

我在解决LeetCode题目《伪回文路径在二叉树中》时，代码在小测试用例下运行正常，但处理大输入时触发堆内存分配错误：

FATAL ERROR: MarkCompactCollector: young object promotion failed Allocation failed - JavaScript heap out of memory

原代码实现 #

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var pseudoPalindromicPaths = function (root) {
    var total = 0
    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])
        }
    }
    dfs(root, [])
    return total;
};

const isPalindromic = (arr) => {
    let numberCounts = {
        "1": 0,
        "2": 0,
        "3": 0,
        "4": 0,
        "5": 0,
        "6": 0,
        "7": 0,
        "8": 0,
        "9": 0
    }
    for (var i = 0; i < arr.length; i++) {
        numberCounts[arr[i]]++
    }
    var res = Object.values(numberCounts)
    var oddCount = 0
    for (var i = 0; i < res.length; i++) {
        if (res[i] % 2 !== 0) {
            oddCount++
        }
        if (oddCount > 1) {
            return false
        }
    }
    return true
}

优化方案 #

1. 消除数组复制的内存开销

原代码每次递归左右子树时，都通过[...parents]复制整个路径数组，这会导致内存中同时存在大量重复的路径副本，对于深度大、节点多的二叉树，内存消耗会急剧上升。

改用回溯法：复用同一个数组，递归进入子树前将当前节点值加入数组，递归返回后再弹出该值，避免复制操作。

2. 用位掩码优化回文判断逻辑

原代码每次判断回文都要遍历整个路径数组统计计数，时间和空间效率都低。由于节点值范围是1-9，我们可以用一个9位的二进制数（位掩码）来记录每个数字出现次数的奇偶性：

• 每一位对应一个数字（比如第0位对应1，第1位对应2，...，第8位对应9）
• 数字出现奇数次时，翻转对应位（异或1 << (val-1)）
• 数字出现偶数次时，再次翻转对应位（变回0）
• 判断是否为伪回文时，只需检查掩码中1的个数是否≤1（可以用mask & (mask - 1) === 0快速判断，当mask是0或2的幂时，结果为0，说明1的个数≤1）

优化后的代码 #

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var pseudoPalindromicPaths = function(root) {
    let total = 0;
    
    const dfs = (node, mask) => {
        // 更新当前节点值对应的位掩码
        mask ^= 1 << (node.val - 1);
        
        // 到达叶子节点，判断是否为伪回文路径
        if (!node.left && !node.right) {
            // 掩码中1的个数≤1时，是伪回文
            if ((mask & (mask - 1)) === 0) {
                total++;
            }
            return;
        }
        
        // 递归左子树，回溯时不需要手动恢复mask，因为参数是值传递
        if (node.left) {
            dfs(node.left, mask);
        }
        // 递归右子树
        if (node.right) {
            dfs(node.right, mask);
        }
    };
    
    dfs(root, 0);
    return total;
};

优化效果说明 #

• 内存方面：不再复制路径数组，递归过程中仅维护一个位掩码（数字类型，占用内存极小），内存复杂度从O(n*h)降至O(h)（h为树的高度）。
• 时间方面：回文判断从O(n)降至O(1)，整体时间复杂度从O(n²)优化为O(n)（n为节点总数），同时避免了大量数组操作的开销。

内容的提问来源于stack exchange，提问作者Jerome