二叉树等和分割：从递归错误到高效算法实践

# 辅助函数：计算子树的总和
def icalculatesum(node):
    if node is None:
        return 0
    return node.value + icalculatesum(node.left) + icalculatesum(node.right)

def splitBinaryTree(tree, balancesum=0):
    if tree is None:
        return 0

    fullsum = icalculatesum(tree) # 重复计算

    # 错误1：这些条件可能导致同时移除两条边
    # 例如：if leftsum + tree.value == rightsum + balancesum
    # 这意味着将 tree 及其左子树作为一个整体，同时从其父节点和右子节点断开
    # 这不符合移除“一条”边的要求

    leftsum = icalculatesum(tree.left) # 重复计算
    rightsum = icalculatesum(tree.right) # 重复计算

    # 错误2：递归调用中的 balancesum 参数传递不正确
    # lefty = splitBinaryTree(tree.left, fullsum - rightsum)
    # righty = splitBinaryTree(tree.right, fullsum - leftsum)
    # 这里的 fullsum - rightsum 并没有正确考虑当前节点 tree.value
    # 导致 balancesum 无法正确代表“另一半”子树的和

    # ... 其他条件判断 ...

    # if lefty != 0 or righty !=0:
    #     return fullsum/2
    # return 0

class BinaryTree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# 辅助函数：计算子树的总和
def icalculatesum(node):
    if node is None:
        return 0
    return node.value + icalculatesum(node.left) + icalculatesum(node.right)

def splitBinaryTree_corrected(tree, balancesum=0):
    if tree is None:
        return 0

    fullsum = icalculatesum(tree) # 当前子树的总和

    # 如果当前子树的和等于期望的 balancesum，则找到了一个分割点
    # 此时，fullsum 就是其中一个子树的和，另一个子树的和就是 balancesum
    # 如果 fullsum == balancesum，意味着整个树可以被分割成两半，每半的和为 fullsum
    if fullsum == balancesum:
        return fullsum

    leftsum = icalculatesum(tree.left)
    rightsum = icalculatesum(tree.right)

    # 递归调用左子树：
    # 传递给左子树的 balancesum 应该包含：
    # 1. 当前节点的值 (tree.value)
    # 2. 当前节点的右子树的总和 (rightsum)
    # 3. 从父节点继承的 balancesum (即除了当前子树之外的其余部分的总和)
    # 这三部分加起来，就是如果从当前节点和左子树的连接处断开，
    # “另一半”树的总和。
    lefty = splitBinaryTree_corrected(tree.left, balancesum + tree.value + rightsum)

    # 递归调用右子树：
    # 传递给右子树的 balancesum 应该包含：
    # 1. 当前节点的值 (tree.value)
    # 2. 当前节点的左子树的总和 (leftsum)
    # 3. 从父节点继承的 balancesum
    righty = splitBinaryTree_corrected(tree.right, balancesum + tree.value + leftsum)

    # 如果任一子树的递归调用返回非零值（即找到了分割点），则返回该值
    return lefty or righty

# 定义二叉树节点（与问题描述一致）
class BinaryTree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# 辅助函数：递归收集所有子树的总和
# 返回一个列表，其中第一个元素是当前子树的根节点总和，
# 后面跟着左右子树的所有子和。
def getAllTreeSums(tree):
    if not tree:
        return [0] # 空树的总和为0

    # 递归获取左右子树的所有子和
    left_sums = getAllTreeSums(tree.left)
    right_sums = getAllTreeSums(tree.right)

    # 当前子树的总和 = 自身值 + 左子树根节点总和 + 右子树根节点总和
    current_tree_sum = tree.value + left_sums[0] + right_sums[0]

    # 将当前子树的总和以及左右子树的所有子和合并返回
    # current_tree_sum 放在列表首位
    return [current_tree_sum] + left_sums + right_sums

def splitBinaryTree_optimized(tree):
    # 收集所有子树的总和
    tree_sums = getAllTreeSums(tree)

    # 整个树的总和是列表的第一个元素
    total_sum = tree_sums[0]

    # 如果总和是偶数，并且其一半的值存在于所有子树和的集合中
    # 那么就找到了一个分割点
    if total_sum % 2 == 0 and (total_sum // 2) in tree_sums:
        return total_sum // 2

    # 否则，无法进行等和分割
    return 0