二叉树等和分割问题：从递归陷阱到高效解法

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

def icalculatesum(node, sumsofar=0):
    if node is None:
        return sumsofar
    sumsofar += node.value
    sumsofar = icalculatesum(node.left, sumsofar)
    sumsofar = icalculatesum(node.right, sumsofar)
    return sumsofar

def splitBinaryTree(tree, balancesum=0):
    if tree is None:
        return 0
    fullsum = icalculatesum(tree)
    print('fullsum is', fullsum, 'balancesum is', balancesum) # 调试信息
    if fullsum == balancesum:
        return fullsum
    leftsum = icalculatesum(tree.left)
    rightsum = icalculatesum(tree.right)

    # 问题1：这些条件判断逻辑错误，可能导致移除两条边
    if leftsum + tree.value == rightsum + balancesum:
        return fullsum / 2
    if rightsum + tree.value == leftsum + balancesum:
        return fullsum / 2
    if leftsum + tree.value + balancesum == rightsum:
        return fullsum / 2
    if rightsum + tree.value + balancesum == leftsum:
        return fullsum / 2

    # 问题2：递归调用时balancesum参数传递错误
    lefty = splitBinaryTree(tree.left, fullsum - rightsum)
    righty = splitBinaryTree(tree.right, fullsum - leftsum)

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

# 辅助函数：计算以node为根的子树的总和
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

    # 计算当前子树（以tree为根）的总和
    current_subtree_sum = icalculatesum(tree)

    # 如果当前子树的和等于目标平衡和，说明找到了一个有效的分割点
    # 此时，整个原始树的总和就是 current_subtree_sum + balancesum
    if current_subtree_sum == balancesum:
        return current_subtree_sum # 或者 (current_subtree_sum + balancesum) / 2

    # 递归处理左子树：
    # 当我们尝试在左子树中寻找切割点时，
    # 另一半子树（即不包含在左子树中的部分）的总和应该是：
    # balancesum（来自父节点的平衡和）+ tree.value（当前节点值）+ icalculatesum(tree.right)（右子树和）
    left_result = splitBinaryTree_corrected(tree.left, balancesum + tree.value + icalculatesum(tree.right))

    # 递归处理右子树：
    # 类似地，当在右子树中寻找切割点时，另一半子树的总和是：
    # balancesum（来自父节点的平衡和）+ tree.value（当前节点值）+ icalculatesum(tree.left)（左子树和）
    right_result = splitBinaryTree_corrected(tree.right, balancesum + tree.value + icalculatesum(tree.left))

    # 如果左子树或右子树的递归调用返回了非零结果，说明找到了分割点
    # 此时，返回分割后的和（即整个原始树总和的一半）
    if left_result != 0:
        return left_result
    if right_result != 0:
        return right_result

    return 0 # 未找到分割点

# 为了使返回值为整个树总和的一半，可以这样调整
def splitBinaryTree_final_corrected(tree):
    total_sum = icalculatesum(tree)
    if total_sum % 2 != 0: # 如果总和是奇数，不可能等分
        return 0
    target_half_sum = total_sum // 2

    # 内部辅助函数，用于递归查找是否存在目标和的子树
    def find_split(node):
        if node is None:
            return 0

        current_node_subtree_sum = icalculatesum(node)
        if current_node_subtree_sum == target_half_sum:
            return target_half_sum

        # 尝试在左右子树中寻找
        left_found = find_split(node.left)
        if left_found != 0:
            return left_found

        right_found = find_split(node.right)
        if right_found != 0:
            return right_found

        return 0

    # 初始调用，从根节点开始查找
    # 需要注意的是，根节点本身不能作为被移除的子树，因为移除它就不是“分割”了
    # 实际的切割点只能是根节点的子节点，或更深层的节点
    # 因此，我们需要确保找到的 `target_half_sum` 对应的子树不是整个原始树本身。
    # 我们可以通过在 `find_split` 中排除根节点来处理，或者在外部检查。

    # 更直接的方法是，在 `find_split` 中，当 `node == tree` 时，
    # 即使 `current_node_subtree_sum == target_half_sum`，也不能直接返回，
    # 因为这表示整个树的和就是 target_half_sum，而不是分割。
    # 实际上，如果整个树的和是 target_half_sum，那意味着 total_sum = 2 * target_half_sum，
    # 这本身就是我们想要的总和，但我们还需要找到一个子树的和等于 target_half_sum。
    # 让我们采用更通用的高效算法来解决这个问题。
    return find_split(tree) # 此处仍需改进，见下文高效算法

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

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

    # 当前树（以tree为根）的总和 = 节点值 + 左子树的总和 + 右子树的总和
    # left_sums[0] 和 right_sums[0] 分别是左右子树的根节点的总和
    current_tree_total_sum = tree.value + left_sums[0] + right_sums[0]

    # 将当前树的总和放在列表开头，然后合并左右子树的子和列表
    # 注意：这里需要排除掉 left_sums 和 right_sums 中可能存在的 0（表示空子树）
    # 但为了简单，直接合并也无妨，因为 0 不会是有效的目标半和（除非总和为0，但题目要求至少一个节点）
    return [current_tree_total_sum, *left_sums, *right_sums]

def splitBinaryTree(tree):
    # 获取所有子树的总和列表
    tree_sums = getAllTreeSums(tree)

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

    # 如果总和为0，且树不止一个节点，这可能意味着所有节点值都是0
    # 但如果只有一个节点，且值为0，则无法分割
    # 题目要求至少一个节点，所以 total_sum 不会是 0 除非所有节点值都是 0。
    # 实际应用中，如果 total_sum 为 0，且树结构复杂，可能需要特殊处理。
    # 但对于正整数节点值，total_sum 为 0 意味着树为空，这与题目至少一个节点的条件矛盾。
    # 假设节点值可以为负数或零。

    # 如果总和为奇数，不可能等分
    if total_sum % 2 != 0:
        return 0

    # 目标半和
    target_half_sum = total_sum // 2

    # 检查是否存在一个子树的和等于目标半和
    # 需要注意的是，整个树的总和本身也可能等于 target_half_sum，
    # 但我们不能将整个树作为“被分割出来的子树”。
    # 所以，我们需要找到一个子树，它的和是 target_half_sum，
    # 并且这个子树不是整个原始树。
    # 由于 tree_sums[0] 是整个树的总和，如果它等于 target_half_sum，
    # 那么 total_sum 必须是 0，这与我们已经处理的 `total_sum % 2 != 0` 矛盾。
    # 实际上，如果 `total_sum == 0`，`target_half_sum = 0`，
    # 并且 `tree_sums` 中除了 `tree_sums[0]` 以外还有 `0`，
    # 那么 `0 in tree_sums` 会返回 True。这表示可以分割。
    # 但通常情况下，我们寻找的是非零的子树和。

    # 最简单的检查方式是：如果 target_half_sum 存在于除了整个树总和之外的任何子树和中。
    # 实际上，`getAllTreeSums` 返回的列表中，`tree_sums[0]` 是整个树的总和。
    # 其他元素是其子树（包括左子树、右子树以及它们各自的子树）的总和。
    # 如果 `target_half_sum` 存在于 `tree_sums` 列表中，且 `target_half_sum != total_sum`，
    # 或者 `target_half_sum == 0` 且列表中有多个 `0` (表示多个空子树可以被切割)。
    # 更严谨的判断是：`target_half_sum` 存在于 `tree_sums` 列表的 `[1:]` 部分。
    # 但如果 `target_half_sum` 是 `0`，且 `tree_sums[0]` 也是 `0`，
    # 那么 `0 in tree_sums` 仍然会是 True，并且 `tree_sums[0]` 也是 `0`。
    # 考虑到题目要求“移除一条边”，这意味着被移除的子树不能是整个树本身。
    # 所以，我们应该在 `tree_sums[1:]` 中查找 `target_half_sum`。

    # 修正：遍历除了根节点总和之外的所有子树和
    # for s in tree_sums[1:]:
    #     if s == target_half_sum:
    #         return target_half_sum
    # return 0

    # 更简洁的写法，只要 target_half_sum 存在于所有子树和中即可
    # 因为如果 total_sum != 0，那么 target_half_sum != total_sum
    # 如果 target_half_sum == total_sum，意味着 total_sum = 0，
    # 此时 target_half_sum 也为 0，并且 0 可能会在 tree_sums 中出现多次。
    if target_half_sum in tree_sums:
        # 额外检查：确保找到的 target_half_sum 不是整个树的总和，
        # 除非整个树的总和就是0，并且可以找到一个子树和也是0（例如，一个空子树被移除）。
        # 但题目要求至少一个节点，所以总和不为0的情况更多。
        # 只要找到了一个子树的和等于 target_half_sum，就说明可以分割。
        # 这种方法隐含地处理了切割点不能是整个树的情况，因为 `getAllTreeSums` 会收集所有子树的和，
        # 包括根节点的子树、孙子树等。
        return target_half_sum

    return 0