分割二叉树代码在某些情况下不起作用

Question

我正在尝试解决Python中分割二叉树的问题。我将发布问题陈述。

编写一个函数，接受至少一个节点的二叉树，并检查是否可以通过删除一条边将该二叉树分成两个总和相等的二叉树。如果这种分割是可能的，则返回每个二叉树的新和，否则返回 0。您不需要返回被删除的边。

测试代码有点像这样

import program
import unittest


class TestProgram(unittest.TestCase):
    def test_case_1(self):
        tree = program.BinaryTree(2)
        tree.left = program.BinaryTree(4)
        tree.left.left = program.BinaryTree(4)
        tree.left.right = program.BinaryTree(6)
        tree.right = program.BinaryTree(10)
        tree.right.left = program.BinaryTree(3)
        tree.right.right = program.BinaryTree(3)
        expected = 16
        actual = program.splitBinaryTree(tree)
        self.assertEqual(actual, expected)

我的 splitBinaryTree 代码如下

# This is an input class. Do not edit.
class BinaryTree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def splitBinaryTree(tree, balancesum=0):
    # Write your code here.
    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)
    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
    lefty = splitBinaryTree(tree.left, fullsum-rightsum)
    righty = splitBinaryTree(tree.right, fullsum-leftsum)

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


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

我在以下测试用例中遇到问题。答案应该是 70 但我的是 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"
}

我正在类似leetcode的平台上练习。请告诉我哪里出了问题，如果需要任何信息，我将很乐意尝试回答。

我尝试删除以前存在的条件

if fullsum%2 !=0:
return 0 

因为我正在递归它。最终它将达到奇数并返回 False/0。

Answer 1

有几个问题：

这个对比：

    if leftsum+tree.value == rightsum+balancesum:
        return fullsum/2

...似乎切割了两条边：它将

tree

及其左子树一起提取，因此

tree

与其父树和右子树分离。所以这是不正确的。下一个

if

块也有同样的问题，但是是镜像的。应从代码中删除这两个

if

块。

以下两个

if

块可以正确执行此操作，因为

tree

并未与其父级分离，而仅与其子级之一分离。

递归调用为第二个参数提供了错误的值：

tree

本身的值没有被考虑在内。所以这个：

    lefty = splitBinaryTree(tree.left, fullsum-rightsum)

...应该是这样的：

    lefty = splitBinaryTree(tree.left, fullsum-rightsum-tree.value)

同样的修复应该适用于

righty

。

通过这些修复，您的代码将可以工作。

更高效的算法

您采取的方法效率不高。你真正需要做的就是找到一个子树，其总和是总和的一半。被切割的边是以该子树的根作为其子项的边。这种模式适合所有可能性：所有边（父、子）都将子树的根作为子。

其次，如果你从下往上增量计算总和，你只会访问一个节点一次，时间复杂度为 O(𝑛)。一旦你收集了这些金额——采用这种自下而上的方法——解决这个挑战就变得微不足道了。

代码

# Recursively collect all tree sums into a list, with the root's sum listed first
def getAllTreeSums(tree):
    if not tree:
        return [0]
    left = getAllTreeSums(tree.left)
    right = getAllTreeSums(tree.right)
    return [tree.value + left[0] + right[0], *left, *right]

def splitBinaryTree(tree):
    tree_sums = getAllTreeSums(tree)
    if tree_sums[0] % 2 == 0 and tree_sums[0] // 2 in tree_sums:
        return tree_sums[0] // 2
    return 0