LeetCode: 129. Sum Root to Leaf Numbers

题目

原题地址：https://leetcode.com/problems/sum-root-to-leaf-numbers/

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

解法

收集所有的 path 上节点的值，然后按照规则计算总和

最简单的办法就是收集所有的 root-to-leaf path，然后按照题目里的计算规则求出总和。 收集 root-to-leaf path 的方法可以参考前面 113. Path Sum II 的方法。

注意：根据计算规则，每个 root-to-leaf path 都需要转换为十进制数字后再求和：

1 -> 2 -> 3 需要转换为数字 123：

1 * 10^2 + 2 * 10^1 + 3 * 10^0 = 123

这个思路的 Python 代码类似下面这样：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root):
        self._numbers = []
        self._curr = []
        total = 0

        self._collect_numbers(root)
        for numbers in self._numbers:
            n = len(numbers) - 1
            # [1, 2, 3] 需要转换为数字 123：
            # 1 * 10^2 + 2 * 10^1 + 3 * 10^0
            for number in numbers:
                total = total + number * (10 ** n)
                n = n - 1

        return total

    def _collect_numbers(self, root):
        if root is None:
            return

        if root.left is None and root.right is None:
            curr = self._curr[:]
            curr.append(root.val)
            self._numbers.append(curr)
            return

        self._curr.append(root.val)

        self._collect_numbers(root.left)
        self._collect_numbers(root.right)

        self._curr.pop()

在收集 root-to-leaf path 的过程中直接求和

还可以直接在收集 root-to-leaf path 的过程中直接求和，省去收集后再做一次求和操作的步骤。

主要思路是：

  • 1 -> 2 -> 3 转换为 123 的过程可以看成是，从上到下遍历的过程中每层都将上一层的结果乘 10 然后再加上当前节点的值： 1 -> 2 -> 3 -> 1 -> 1 * 10 + 2 -> (1 * 10 + 2) * 10 + 3 = 123
  • 同时如果是一层一层的往下计算的话，还可以省去一些重复的计算步骤，把上层的结果传递给下层这样如果下层刚好有 leaf 节点就不需要从头到尾再重复计算一遍了。

这个思路的 Python 代码类似下面这样：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sumNumbers(self, root):
        self._total = 0

        self._collect(root, 0)

        return self._total

    def _collect(self, root, pre_deepth_sum):
        if root is None:
            return

        new_deepth_sum = pre_deepth_sum * 10 + root.val

        if root.left is None and root.right is None:
            self._total += new_deepth_sum
            return

        # 将上层计算结果传递给下层
        self._collect(root.left, new_deepth_sum)
        self._collect(root.right, new_deepth_sum)

Comments