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)

我的实现代码 #

# 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"
}

已尝试的调整 #

我之前移除了如下条件：

if fullsum%2 !=0:
return 0 

因为我认为递归过程中最终会遇到奇数总和并返回0，但问题依然存在，请求帮忙排查代码错误。

内容的提问来源于stack exchange，提问作者Karina