Python计算子树节点值之和的最小值程序

树结构是数据结构中常用的一种，它的节点间存在明确的父子关系。在实际开发中我们有时需要计算树中子树节点值之和的最小值，这也是一种常见的算法问题。

问题描述

给定一颗二叉树，每个节点都有一个整型值，现在需要找到一个子树，其节点值之和是所有子树中最小的。

在该例子中，节点5所在的子树的节点值之和是最小的，值为8。

算法思路

本问题可以通过遍历整棵树的方式，来计算每个子树根节点及其子节点之和，从而找到节点值之和最小的子树。

我们可以自下而上遍历整棵树，每个节点都通过递归遍历，计算出以该节点为根的子树的节点值之和，并比较与之前的最小值，更新最小值的根节点和节点值之和。

具体算法步骤如下：

定义一个全局变量minValue，用于保存当前找到的最小节点值之和，初始值设置为正无穷。
定义一个辅助函数dfs，用于递归计算节点值之和以及更新minValue。
在dfs中，计算当前节点值加上左右子树节点值之和的值sum，与minValue比较，如果小于minValue，则更新minValue和minNode。
最后返回该节点值加上左右子树节点值之和的值sum。

下面是示例代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.minValue = float('inf')  # 设定初值为正无穷
        self.minNode = None

    def dfs(self, root):
        if not root: 
            return 0

        left_sum = self.dfs(root.left)
        right_sum = self.dfs(root.right)

        sum = root.val + left_sum + right_sum

        if sum < self.minValue:
            self.minValue = sum
            self.minNode = root

        return sum

    def findSubtree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.dfs(root)

        return self.minNode