在 Python 中找到二叉树路径中所有数字的和

在二叉树中，路径定义为从根节点开始，一直到叶子节点的节点序列。而二叉树路径的数字之和则是路径中每个节点值的累加总和。在本文中，我们将介绍如何使用 Python 编程语言来查找二叉树路径中所有数字的和。

二叉树节点的定义

在开始编写代码之前，我们首先需要定义二叉树节点的结构。二叉树节点一般包含三个基本元素：一个值、一个左节点和一个右节点。在 Python 中，二叉树节点的定义可以如下所示：

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

查找二叉树路径中所有数字的和

在二叉树中找到路径的总和需要使用深度优先遍历算法（Depth First Search，DFS）。深度优先遍历遍历每个节点的方法通常有两种：前序遍历和后序遍历。在前序遍历中，根节点首先遍历，然后是左子树，之后是右子树。在后序遍历中，左子树遍历后右子树，最后才遍历根节点。

在这个问题中，我们将采用前序遍历的方式来找到路径总和。每当我们在递归中进入一个新的节点时，我们需要计算当前节点值与其父节点到根节点的路径和的总和。我们可以将当前节点值加到路径总和变量中，并将其传递到函数递归调用中。如果当前节点是叶子节点（即没有左子树或右子树），那么我们就没有必要继续递归下去了。

下面是查找二叉树路径中所有数字的和的示例代码：

class Solution:
    def sumNumbers(self, root):
        if root is None:
            return 0

        self.total_sum = 0
        def dfs(node, path_sum):
            if node.left is None and node.right is None:
                self.total_sum += path_sum * 10 + node.val
                return

            if node.left:
                dfs(node.left, path_sum * 10 + node.val)
            if node.right:
                dfs(node.right, path_sum * 10 + node.val)

        dfs(root, 0)
        return self.total_sum

在 DFS 函数中，我们通过递归来遍历每个节点，并记录路径总和。当我们遇到叶子节点时，我们就计算路径总和，并跳出递归。

测试示例

为了测试我们的代码，我们需要创建一个二叉树，并计算在其中找到路径的数字之和。我们可以使用以下代码创建一个简单的二叉树：

# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

然后我们就可以使用我们上面编写的代码来计算路径总和。下面是测试代码：

# 测试结果
s = Solution()
print(s.sumNumbers(root))

输出结果应该为 25，因为我们有两个路径，即 12 和 13。它们的数字之和是 (110+2) + (110+3) = 25。

结论

使用 Python 编程语言查找二叉树路径中所有数字的和并不难，我们只需要采用深度优先遍历算法即可。通常情况下，可以通过前序遍历或后序遍历来找到路径总和。在实际编写代码时，我们需要创建一个 TreeNode 类来表示二叉节点，并使用递归来找到路径总和。