深入理解二叉树等和分割问题

DDD

发布时间：2025-11-20 12:20:43

156人浏览过

来源于php中文网

原创

深入理解二叉树等和分割问题

本文旨在探讨如何判断一个二叉树是否可以通过移除一条边被分割成两个和相等的子树，并返回该和。文章首先分析了一种常见的递归解法及其潜在问题，提供了详细的修正方案，随后介绍了一种更高效的自底向上遍历算法，通过一次遍历收集所有子树和，从而在O(N)时间复杂度内解决问题，并提供了完整的Python实现代码和注意事项。

二叉树等和分割问题概述

二叉树等和分割问题要求我们编写一个函数，接收一个至少包含一个节点的二叉树作为输入。该函数需要判断是否存在这样一条边，移除它后可以将原二叉树分割成两个独立的二叉树，且这两个二叉树的节点值之和相等。如果存在这样的分割，函数应返回分割后每个子树的总和；否则，返回0。

为了更好地理解和解决这个问题，我们首先定义一个基本的二叉树节点类：

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

递归解法分析与修正

一种直观的思路是采用递归方式遍历树的每个节点，并尝试以该节点为根的子树作为其中一个分割点。在递归过程中，我们需要计算当前子树的总和，并判断是否与另一个部分的和相等。

初始递归尝试中的常见问题

在最初的递归尝试中，常常会遇到以下几个问题：

不正确的边缘移除逻辑： 有些判断条件可能错误地假设移除了多条边，例如同时将当前节点与其父节点和其某个子节点断开。正确的“移除一条边”意味着将一个子树从其父节点处分离。
balancesum 参数传递错误： 在递归调用中，用于表示另一部分树的和（balancesum）的计算方式可能不准确，没有充分考虑当前节点的值及其兄弟子树的值。
冗余判断： 一些本应由更深层递归处理的条件被提前判断，导致代码复杂且可能出错。

修正后的递归算法

为了解决上述问题，我们可以对递归函数进行如下修正：

首先，我们需要一个辅助函数来计算任意给定子树的总和。

def calculate_subtree_sum(node):
    if node is None:
        return 0
    return node.value + calculate_subtree_sum(node.left) + calculate_subtree_sum(node.right)

然后，修正 splitBinaryTree 函数。核心思想是，当我们递归到某个节点 tree 时，我们尝试将以 tree.left 或 tree.right 为根的子树作为其中一个分割点。balancesum 参数应代表在当前递归层级中，除了当前子树以外的“剩余部分”的总和。

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

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

    # 如果当前子树的总和等于我们期望的另一半的和，说明找到了一个分割点
    # 此时，整个树的总和就是 current_subtree_total_sum + balancesum
    # 如果两者相等，则说明 current_subtree_total_sum 恰好是总和的一半
    if current_subtree_total_sum == balancesum:
        return current_subtree_total_sum

    # 计算左右子树的和，用于构建递归调用的 balancesum
    left_child_sum = calculate_subtree_sum(tree.left)
    right_child_sum = calculate_subtree_sum(tree.right)

    # 递归调用左子树：
    # 当我们尝试在左子树中寻找分割点时，
    # 另一半树（balancesum）应该包括：
    # 1. 之前传递下来的 balancesum
    # 2. 当前节点的值 tree.value
    # 3. 当前节点的右子树的总和 right_child_sum
    left_split_result = splitBinaryTree_corrected_recursive(
        tree.left, balancesum + tree.value + right_child_sum
    )

    # 递归调用右子树：
    # 同理，当在右子树中寻找分割点时，
    # 另一半树（balancesum）应该包括：
    # 1. 之前传递下来的 balancesum
    # 2. 当前节点的值 tree.value
    # 3. 当前节点的左子树的总和 left_child_sum
    right_split_result = splitBinaryTree_corrected_recursive(
        tree.right, balancesum + tree.value + left_child_sum
    )

    # 如果任何一个递归调用找到了有效的分割，则返回该结果
    return left_split_result or right_split_result

注意事项：

Adrenaline

软件调试助手，识别和修复代码中错误

下载

此修正版本移除了不正确的 if 条件判断，因为那些情况最终会被更深层的递归调用正确处理。
balancesum 的计算至关重要，它必须准确地代表当前递归节点之外的树的总和。
这种方法虽然修正了逻辑错误，但仍然存在效率问题，因为 calculate_subtree_sum 在每个节点都会被多次调用，导致重复计算。

更高效的算法：自底向上遍历

为了提高效率，我们可以采用自底向上的方法，在一次遍历中计算所有子树的总和，并存储起来。这种方法可以避免重复计算，将时间复杂度优化到O(N)，其中N是树中的节点数。

算法思路

收集所有子树和： 从叶子节点开始，向上递归计算每个子树的总和。在计算的同时，将每个子树的总和存储在一个列表中。根节点的总和将是列表中的第一个元素。
检查分割条件：
- 首先，获取整个树的总和（即列表中的第一个元素）。
- 如果整个树的总和是奇数，则不可能将其分割成两个和相等的子树，直接返回0。
- 如果总和是偶数，计算目标和（总和的一半）。
- 检查存储所有子树和的列表中是否存在这个目标和。如果存在，说明可以找到一个子树，其和恰好是整个树总和的一半，从而实现等和分割。

实现代码

# 辅助函数：递归收集所有子树的和
def getAllTreeSums(tree):
    # 如果节点为空，其子树和为0
    if not tree:
        return [0]

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

    # 当前子树（以tree为根）的总和 = tree.value + 左子树根的和 + 右子树根的和
    current_tree_root_sum = tree.value + left_sums[0] + right_sums[0]

    # 将当前子树的总和放在列表开头，然后拼接左右子树的所有和
    # 这样，最终返回的列表的第一个元素总是整个树的总和
    return [current_tree_root_sum, *left_sums, *right_sums]

def splitBinaryTree(tree):
    # 1. 收集所有子树的和
    # getAllTreeSums 返回的列表第一个元素是整个树的总和
    tree_sums = getAllTreeSums(tree)

    # 整个树的总和
    total_sum = tree_sums[0]

    # 2. 检查分割条件
    # 如果总和为0（空树或所有节点值为0），或总和为奇数，则无法分割
    if total_sum == 0 or total_sum % 2 != 0:
        return 0

    # 目标分割和
    target_half_sum = total_sum // 2

    # 检查是否存在一个子树，其和恰好是目标分割和
    # 这里的 `tree_sums` 包含了所有可能的子树和（包括根节点自身形成的子树和）
    if target_half_sum in tree_sums:
        return target_half_sum

    return 0

示例测试用例（来自问题描述）：

{
  "nodes": [
    {"id": "1", "left": "9", "right": "20", "value": 1},
    {"id": "9", "left": "5", "right": "2", "value": 9},
    {"id": "20", "left": "30", "right": "10", "value": 20},
    {"id": "30", "left": null, "right": null, "value": 30},
    {"id": "10", "left": "35", "right": "25", "value": 10},
    {"id": "35", "left": null, "right": null, "value": 35},
    {"id": "25", "left": null, "right": null, "value": 25},
    {"id": "5", "left": null, "right": null, "value": 5},
    {"id": "2", "left": "3", "right": null, "value": 2},
    {"id": "3", "left": null, "right": null, "value": 3}
  ],
  "root": "1"
}

对于上述树结构，其节点值如下：