难度: Medium
Submission
运行时间: 22 ms
内存: 0.0 MB
class Solution:
def pathSum(self, nums: List[int]) -> int:
binaryTree = dict()
for num in nums:
key = num // 10
val = num % 10
binaryTree[key] = val
def traverse(cur: int, preSum: int) -> int:
depth, pos = cur // 10, cur % 10
leftChild = (depth + 1) * 10 + pos * 2 - 1
rightChild = (depth + 1) * 10 + pos * 2
if leftChild not in binaryTree and rightChild not in binaryTree:
return preSum + binaryTree[cur]
res = 0
if leftChild in binaryTree:
res += traverse(leftChild, preSum + binaryTree[cur])
if rightChild in binaryTree:
res += traverse(rightChild, preSum + binaryTree[cur])
return res
return traverse(nums[0] // 10, 0)
Explain
该题解的思路是将给定的数字数组转化为一个字典，用于表示二叉树。字典的键为节点编号，值为节点值。然后使用深度优先搜索遍历二叉树，计算从根节点到每个叶子节点的路径和，最后返回所有路径和的总和。在遍历过程中，通过节点编号计算左右子节点的编号，判断子节点是否存在，递归计算路径和。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def pathSum(self, nums: List[int]) -> int:
# 构建二叉树字典
binaryTree = dict()
for num in nums:
key = num // 10
val = num % 10
binaryTree[key] = val
def traverse(cur: int, preSum: int) -> int:
depth, pos = cur // 10, cur % 10
leftChild = (depth + 1) * 10 + pos * 2 - 1
rightChild = (depth + 1) * 10 + pos * 2
# 叶子节点，返回当前路径和
if leftChild not in binaryTree and rightChild not in binaryTree:
return preSum + binaryTree[cur]
res = 0
# 递归计算左子树的路径和
if leftChild in binaryTree:
res += traverse(leftChild, preSum + binaryTree[cur])
# 递归计算右子树的路径和
if rightChild in binaryTree:
res += traverse(rightChild, preSum + binaryTree[cur])
return res
# 从根节点开始遍历
return traverse(nums[0] // 10, 0)
Explore
在构建二叉树字典时，`num // 10`作为键，`num % 10`作为值的做法是为了从给定的数字中分离出节点的位置信息和节点的值。在此题中，每个数字由三位组成，其中最左边的一位代表节点的层次（depth），中间的一位代表该层次中的位置（position），最右边的一位代表节点的值。使用`num // 10`可以去掉最后一位，从而得到由层次和位置组成的两位数，这两位数作为键，可以唯一标识一个节点的位置。而`num % 10`则直接获取该节点的值。
该公式是基于二叉树的层次和位置编号规则来计算子节点的编号。在二叉树中，如果一个节点位于第`depth`层，位置为`pos`，那么它的左子节点将位于第`depth+1`层，位置为`2*pos-1`；右子节点位于同一层，位置为`2*pos`。因此，公式`(depth + 1) * 10 + pos * 2 - 1`用于计算左子节点的编号，`(depth + 1) * 10 + pos * 2`用于计算右子节点的编号。这种编号方法便于从父节点直接计算出子节点的位置编号，保持树结构的清晰和操作的简便性。
在本题的上下文中，我们假设给定的输入数据是完整的，即不存在数据缺失的情况。因此，如果某个节点的左子节点或右子节点的编号不在字典中，我们可以认为这是因为该节点是叶子节点。在实际应用中，若有可能存在数据不完整的情况，那么这种方法可能需要调整，以确保正确判断叶子节点。
在递归函数`traverse`中，`preSum + binaryTree[cur]`作为参数传递给子递归调用主要是为了在递归过程中累积当前路径上的节点值之和。这样做的优势是可以在每个递归调用中直接得到从根节点到当前节点的路径和，无需在每次返回时重新计算或存储路径上的节点值。这种方法提高了效率，减少了重复计算，并且使代码更加简洁和易于理解。