LeetCode 666. 路径总和 IV

2026-04-11 HGNULB 约 9 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 666. 路径总和 IV

题意分析

输入不是一棵真正的树，而是一个升序排列的三位数数组。每个三位数把一个节点的三条信息压在一起：百位是它所在的深度，十位是它在这一层从左往右数的编号，个位是它的值。要求的是这棵树上所有从根到叶子的路径的数值之和再相加。

编号规则是本题的题眼，必须读准：十位上的编号是按满二叉树来编的，也就是说第 d 层理论上有 $2^{d-1}$ 个位置，编号从 1 到 $2^{d-1}$，实际存在的节点只是占了其中一部分位置。它不是「这一层第几个出现的节点」，所以绝不能按数组里的先后顺序重新编号。

约束里写明深度小于 5、编号最多到 8、值是一位数，这几条合起来保证了三位数编码不会歧义，也保证了整棵树的节点数很少。另外要注意叶子的定义是「左右两个孩子都不存在」，而不是「所在层是最深的一层」——一棵树完全可以在第二层就有叶子，同时第三层还有别的节点。

边界上，输入至少含一个节点，所以根一定存在于第 1 层第 1 号位置；只有一个节点时，这个节点自己就是叶子，答案就是它的值。

解法：哈希表 + 深度优先搜索

核心思路

最容易想到的做法是先把编码还原成真正的树：新建一批 TreeNode，再按父子关系把它们连起来，最后跑一遍常规的路径和统计。这条路能通，但仔细一想会发现一件事——为了连边，你必须先解决「给定一个节点，怎么找到它的两个孩子」这个问题，而这恰恰是整道题唯一的难点。难点解决之后再额外建一棵树，纯属多此一举。

瓶颈其实不在遍历，而在于「定位」：只要能在常数时间里回答「深度 d、编号 p 的位置上有没有节点、值是多少」，就能直接在编码上做深度优先搜索。

满二叉树的编号给了现成的公式：深度为 d、编号为 p 的节点，它的左孩子在深度 d + 1 的编号 $2p - 1$ 处，右孩子在编号 $2p$ 处。于是把 $(d, p)$ 压成一个整数键 $d \times 10 + p$ 存进哈希表，值取节点的数值，定位问题就解决了。这里用十进制拼接是安全的：真实节点的键最大是 $4 \times 10 + 8 = 48$，而所有会被查询到的第 5 层的键至少是 $5 \times 10 + 1 = 51$，两者不会撞上。

递归函数的语义定成：dfs(d, p, prefix) 中 prefix 是从根一路走到 $(d, p)$ 的父节点为止累积的和，函数返回「以 $(d, p)$ 为根的子树里，所有根到叶路径和的总和」，位置为空时返回 0。这个定义让空位置和真实节点在返回值上完全同构，父层不需要事先判断孩子存不存在。

解题步骤

先扫一遍 nums，把每个三位数拆成深度、编号、数值三部分，以 $d \times 10 + p$ 为键写入哈希表。拆分要用 num / 100、(num / 10) % 10、num % 10，中间那一项必须再取一次模，否则会把编号和数值粘在一起。

从 dfs(1, 1, 0) 开始递归。根固定在深度 1 编号 1，前缀和从 0 起步，这样第一层加完之后 prefix 恰好等于根的值。

进入 dfs 后先查键是否存在，不存在直接返回 0。这一步同时承担了两个职责：既是递归出口，也让上层可以无脑地对两个孩子都发起递归。

存在则令 currentSum = prefix + 当前节点值，然后算出两个孩子的键。

若两个孩子的键都不在哈希表里，说明当前节点是叶子，直接返回 currentSum——这就是一条完整路径的和。判断依据必须是「这个节点自己的两个孩子都不存在」，而不是「更深的层里有没有节点」。

否则返回两个孩子递归结果之和，把 currentSum 作为新的前缀传下去。不存在的那一侧会在下一层直接返回 0，不需要在这里特判。

以 nums = [113, 215, 221, 315] 走一遍：解码后哈希表是 {11: 3, 21: 5, 22: 1, 31: 5}，对应的树是根节点值 3，它的左孩子值 5、右孩子值 1，左孩子还有一个左孩子值 5。从 dfs(1, 1, 0) 开始，键 11 存在，currentSum = 0 + 3 = 3，两个孩子的键是 21 和 22，都存在，所以不是叶子，返回 dfs(2, 1, 3) + dfs(2, 2, 3)。进入 dfs(2, 1, 3)，键 21 存在，currentSum = 3 + 5 = 8，孩子键是 $3 \times 10 + 1 = 31$ 和 32，其中 31 存在，仍不是叶子，返回 dfs(3, 1, 8) + dfs(3, 2, 8)。dfs(3, 1, 8) 里键 31 存在，currentSum = 8 + 5 = 13，孩子键 41、42 都不存在，判定为叶子，返回 13；dfs(3, 2, 8) 里键 32 不存在，返回 0。于是 dfs(2, 1, 3) 得到 13。再看 dfs(2, 2, 3)，键 22 存在，currentSum = 3 + 1 = 4，孩子键是 33 和 34，都不存在，判定为叶子，返回 4。最终答案是 13 + 4 = 17，对应两条路径 3 + 5 + 5 和 3 + 1，与手算一致。

代码实现

// 对于深度为 d、位置为 p 的节点，左孩子位置是 2 * p - 1，右孩子位置是 2 * p。
class Solution {
    public int pathSum(int[] nums) {
        Map<Integer, Integer> values = new HashMap<>();
        for (int num : nums) {
            int depth = num / 100;
            int position = (num / 10) % 10;
            int value = num % 10;
            values.put(depth * 10 + position, value);
        }

        return dfs(values, 1, 1, 0);
    }

    private int dfs(Map<Integer, Integer> values, int depth, int position, int prefixSum) {
        int key = depth * 10 + position;
        if (!values.containsKey(key)) {
            return 0;
        }

        int currentSum = prefixSum + values.get(key);
        int nextDepth = depth + 1;
        int leftPosition = position * 2 - 1;
        int rightPosition = position * 2;
        int leftKey = nextDepth * 10 + leftPosition;
        int rightKey = nextDepth * 10 + rightPosition;

        if (!values.containsKey(leftKey) && !values.containsKey(rightKey)) {
            return currentSum;
        }

        return dfs(values, nextDepth, leftPosition, currentSum)
            + dfs(values, nextDepth, rightPosition, currentSum);
    }
}

// 对于深度为 d、位置为 p 的节点，左孩子位置是 2 * p - 1，右孩子位置是 2 * p。
func pathSum(nums []int) int {
    values := make(map[int]int, len(nums))
    for _, num := range nums {
        depth := num / 100
        position := (num / 10) % 10
        value := num % 10
        values[depth*10+position] = value
    }

    var dfs func(depth int, position int, prefixSum int) int
    dfs = func(depth int, position int, prefixSum int) int {
        key := depth*10 + position
        value, exists := values[key]
        if !exists {
            return 0
        }

        currentSum := prefixSum + value
        nextDepth := depth + 1
        leftPosition := position*2 - 1
        rightPosition := position * 2
        leftKey := nextDepth*10 + leftPosition
        rightKey := nextDepth*10 + rightPosition

        if _, hasLeft := values[leftKey]; !hasLeft {
            if _, hasRight := values[rightKey]; !hasRight {
                return currentSum
            }
        }

        return dfs(nextDepth, leftPosition, currentSum) + dfs(nextDepth, rightPosition, currentSum)
    }

    return dfs(1, 1, 0)
}

复杂度分析

时间复杂度：$O(n)$，其中 n 是编码数组的长度。建表扫一遍是 $O(n)$；递归时每个真实存在的节点只被展开一次，对空位置的查询次数不超过真实节点数的两倍，哈希查找是常数级。

空间复杂度：$O(n)$，哈希表存下全部 n 个节点；递归栈深度等于树高，本题不超过 4，是常数级。

关键点总结

当输入用编码而不是指针描述一棵树时，先问「能不能直接在编码上遍历」，通常比先还原成真实结构再遍历更省事；本题的建树步骤其实完全可以省掉。

满二叉树的位置编号可以由父推子，这条性质是把散乱的编码重新组织成树的唯一桥梁，也是堆、线段树等结构共用的下标技巧。

把「位置是否存在」交给哈希表回答，递归函数对空位置返回 0，就能让存在与不存在在返回值层面同构，父层不需要任何前置判断，代码会短一大截。

叶子的判定必须落在「自己的两个孩子都不存在」上，用层数最深与否来判断是本题最隐蔽的坑。

面试视角：面试官会重点问「为什么 $d \times 10 + p$ 这种拼键不会冲突」。要能算给他看：真实键最大 48，被查询的第 5 层键最小 51，两个区间不相交；同时补一句「如果深度上限放大，编号会超过 9，就必须换成更宽的进制或直接用二元组」，展示你知道这个技巧的适用边界。

面试视角：主动对比一下「先建树再求和」与「直接在编码上递归」两种方案，说明后者省掉的是一次结构复制而不是复杂度；能讲清楚取舍，比只写出能过的代码更有说服力。

易错点总结

错误写法：解码编号时写成 num % 100 而漏掉再除以 10：nums = [113, 215, 221] → 节点 215 的编号被算成 15，键变成 35，既定位不到真实位置，也可能与别的深度的键混淆，路径和完全错乱。

错误写法：不判断叶子，在每个节点都把 currentSum 计入答案：nums = [113, 215, 221] → 内部节点 3 也被当成路径终点，返回 3 + 8 + 4 = 15，而正确答案是 12。

错误写法：孩子编号按 0 基公式写成 $2p$ 与 $2p+1$：nums = [113, 215, 221] → 根的孩子被算到编号 2 和 3 上，编号 1 的节点 5 被彻底忽略，答案变成 4 而不是 12。

错误写法：位置不存在时返回 prefix 而不是 0：nums = [113, 221] → 根的左孩子不存在却贡献了 3，答案变成 7 而不是 4。

错误写法：叶子判定写成「哈希表里没有更深的层」：nums = [113, 215, 221, 315] → 因为第 3 层有节点，编号 (2, 2) 的叶子不被认作叶子，它那条路径的 4 从未被计入，答案变成 13 而不是 17。

错误写法：无视编号字段，按 nums 中的出现顺序重新给每层编号：nums = [113, 222, 332] → 位置 2 的节点被当成位置 1，于是去找编号 1 和 2 的孩子，真正在编号 3 上的节点被漏掉，答案算成 5 而不是 7。

错误写法：把 $d \times 10 + p$ 这套拼键直接搬到深度更大的同类题上：一旦某层编号超过 9 → 十位会向百位进位，不同深度的键相互碰撞，读到的是别的节点的值，而这类错误在小样例上完全暴露不出来。

相似题目

题目	难度	考察点
112. 路径总和	简单	只判断是否存在等于目标值的根到叶路径，找到即可提前返回
113. 路径总和 II	中等	要输出所有满足条件的路径，需要回溯维护当前路径
437. 路径总和 III	中等	路径起点终点都不固定，靠前缀和加哈希表统计
129. 求根节点到叶节点数字之和	中等	同为累加根到叶的结果，但前缀是按十进制拼数而非求和