2020-05-28-summing-root-to-leaf-numbers

确保翻译不显得太生硬。确保翻译注释。
这个文件是用Markdown格式写的。不要把它当作XML或HTML。
不要翻译任何[!NOTE]、[!WARNING]、[!TIP]、[!IMPORTANT]或[!CAUTION]。
不要翻译任何实体，如变量名、函数名、类名，或占位符如@@INLINE_CODE_x@@或@@CODE_BLOCK_x@@，但保留它们在文件中。
不要翻译任何URL或路径，但保留它们在文件中。
请从左到右写输出。

标题：求根到叶节点数字之和
slug：求根到叶节点数字之和
作者：Raivat Shah
作者职位：新加坡国立大学计算机科学专业学生
作者链接：https://github.com/raivatshah
作者头像链接：https://github.com/raivatshah.png
标签：[leetcode, 树, 问题解决]
隐藏目录：true

求根到叶节点数字之和是LeetCode上一个有趣的题目。这道题属于中等难度，涉及二叉树。本文将详细解释该题的解法。

我假设你已经熟悉Python以及二叉树的概念。如果你还不熟悉，可以阅读这篇文章来入门。

题目描述

给定一棵二叉树，其节点包含值0-9，我们需要计算所有从根节点到叶节点路径所构成的数字之和。叶节点是指没有子节点的节点。在二叉树中，从根到叶的路径总是唯一的。以下是所需解法的预期行为：

在左侧的树中，输出为25。25是12和13之和，这两个数字分别是从1开始遍历每个叶节点时形成的。在右侧的树中，输出为1026，它是三个数字495、491和40之和。

观察与启发

1. 要构造一个数字，我们需从根节点开始遍历到叶节点，将数字依次拼接起来，其中最高位数字位于根节点，最低位数字位于叶节点。我们会先访问一些离根节点更近的叶节点，再访问其他节点。这表明深度优先搜索会非常有用。

2. 数字的构造是逐步进行的，且有一定的相似性：例如，右侧树中的495和491的区别仅在于最后一位数字。如果我们去掉5并插入一个1，就能得到下一个所需的数字。一个数字本质上是由叶节点的数字加上所有祖先节点的数字拼接而成。因此，同一子树内的数字会有共同的前缀。

3. 最后，注意到这道题涉及树结构，因此递归解法会很有帮助。

解法

我们可以对树进行一次pre-order遍历，在遍历过程中逐步构造数字，并利用同一子树内节点所构成的数字有共同前缀的特点。当我们完成一个子树的数字构造后，可以回溯到另一个子树继续处理。

让我们创建一个Solution类来封装我们的解法。

class Solution:
  def sum_numbers(self, root: TreeNode) -> int:
​

题目给出的方法签名只有一个参数：root，类型为TreeNode . A TreeNode。TreeNode类定义如下（来自LeetCode）：

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
​

根据观察#2，注意到将一个节点的数字添加到其祖先节点，可以通过将祖先节点构成的数字的所有数字向右移动一位，然后加上当前节点的数字来实现。这些数字的移动可以通过将祖先节点构成的数字乘以10来完成（因为我们使用的是十进制）。例如：

495 = 49 × 10 + 5

Thus, we can keep track of the current digits in an integer. This is important because we won't incur extra storage space for higher input sizes. We can pass around this value in the function parameter itself. Since the method signature given can only have one parameter, let's create a sum_root_to_leaf_helper method.

We can think of the sum_root_to_leaf_helper method recursively and process each node differently based on whether or not it is a leaf.

• If the node is a leaf, we want to add its digit to our current digits by moving all the other digits to the right. We also want to return this value (since we'll backtrack from here).

• If it is not a leaf, we want to add the digit to our current digits by moving all the other digits to the right. We also want to continue constructing the number by traversing down this node's left and right subtrees.

If the current node is a None, we can simply return 0 because it doesn't count.

Thus, our sum_root_to_leaf_helper方法如下：

def sum_root_to_leaf_helper(node, partial_sum=0):
  if not node:
    return 0
  partial_sum = partial_sum * 10 + node.val
  # Leaf
  if not node.left and not node.right:
    return partial_sum
  # Non Leaf
  return (sum_root_to_leaf_helper(node.left, partial_sum) + \
    sum_root_to_leaf_helper(node.right, partial_sum))
​

我们为部分和设置了一个默认值0。

在主方法中，我们将sum_root_to_leaf_helper方法作为嵌套方法，并直接传入节点参数。最终，我们的解法如下：

class Solution:
  def sumNumbers(self, root: TreeNode) -> int:
    def sum_root_to_leaf_helper(node, partial_sum=0):
      if not node:
        return 0
      partial_sum = partial_sum * 10 + node.val
      # Leaf
      if not node.left and not node.right:
        return partial_sum
      # Non Leaf
      return (sum_root_to_leaf_helper(node.left, partial_sum) + \
        sum_root_to_leaf_helper(node.right, partial_sum))

    return sum_root_to_leaf_helper(root)
​

算法复杂度分析

当我们提出一种解法时，分析其算法复杂度非常重要，不仅是为了评估性能，还能发现改进空间，反思自己的解题能力。我们应始终问自己：“我们能否做得比X更好？”其中X是我们当前解法的复杂度。

时间：

我们的解法是对深度优先搜索前序遍历的一种改进，我们恰好访问每个节点一次，并执行简单的计算（通过整数乘法移动数字）。因此，我们的运行时间就是O(N) where N represents the number of nodes in the given tree. A solution better than O(N) doesn't seem possible because to construct a number from digits, we need to know all the digits (and thus visit all nodes).

Space:

In terms of storage, we incur a high cost in the recursion call stack that builds up as our sum_root_to_leaf_helper calls itself. These calls build-up as one waits for another to finish.

The maximum call stack is dependent upon the height of the binary tree (since we start backtracking after we visit a leaf), giving a complexity of O(H) where H is the height of the binary tree. In the worst case, the binary tree is skewed in either direction and thus H = N. Therefore, the worst-case space complexity is O(N).

You can read this article to know more about recursion call stacks.

It is possible to do better than O(N)，采用Morris前序遍历实现。基本思路是临时连接节点与其前驱节点。你可以在这里了解更多相关内容[https://www.sciencedirect.com/science/article/abs/pii/0020019079900681]。

结语

希望这篇帖子对你有所帮助！如果你有任何反馈、评论或建议，请回复本帖告诉我。

致谢

感谢Advay、Kevin、Louie对本文的审阅，以及Yangshun提出的将其作为博客文章的想法。

免责声明：
本文档采用基于机器的 AI 翻译服务进行翻译。尽管我们力求准确，但请注意，自动翻译可能存在错误或不准确之处。应以原文语言版本的文档作为权威依据。如需获取关键信息，建议使用专业的人工翻译。对于因使用本翻译而产生的任何误解或误读，我们概不负责。