如何使用 Python 计算树枝的总和？

Question

我目前正在练习 python，但我遇到了二叉树的问题。我认为我在 python 方面相当不错，但我在二叉树方面遇到了困难。

问题是：

给出了函数定义的第一行，所以我需要按原样使用它，但不确定如何计算分支总和。

def solution(arr):
    root = arr[0]

   for i in arr.index(i):
       left = sum(arr[i]-arr[0])
       right = sum(arr[i+1]-arr[0])

   if left > right:
       return "Left"

   elif left < right:
        return "Right"

   else:
       return ""

我得到的错误是

 Traceback (most recent call last):
  File "/usercode/file.py", line 36, in <module>
    test()
  File "/usercode/file.py", line 34, in test
    json.dumps(solution(*input), separators=(',', ':')))
  File "/usercode/file.py", line 5, in solution
    for i in arr.index(i):
UnboundLocalError: local variable 'i' referenced before assignment

Answer 1

可以使用递归的方法来求解。

下面是解决代码。你可以 see complete code here:

class TreeNode:

    def __init__(self, lValue, lLeft=None, lRight=None):
        self.Value = lValue
        self.Left = lLeft
        self.Right = lRight


def addNode(root, lVal):
    newNode = TreeNode(lVal)
    queue = []
    queue.append(root)
    while(len(queue) > 0):
        node = queue.pop(0)
        if node.Left is None:
            node.Left = newNode
            break

        if node.Right is None:
            node.Right = newNode
            break

        queue.append(node.Left)
        queue.append(node.Right)


def createBinaryTree(lList):
    binaryTree = None
    for i in lList:
        if i is not -1:
            if binaryTree is not None:
                addNode(binaryTree, i)
            else:
                binaryTree = TreeNode(i)

    return binaryTree


def sum(node):
    if node is None:
        return 0
    lLeftVal = sum(node.Left)
    lRightVal = sum(node.Right)

    return (lLeftVal + lRightVal + node.Value)


def solution(binaryTree):
    if binaryTree == None:
        return ""

    if( sum(binaryTree.Left) > sum(binaryTree.Right) ):
        return "Left"
    else:
        return "Right"


def main():
    binaryTree = createBinaryTree([3,6,2,9,-1,10])
    print(solution(binaryTree))


main()

如何使用 Python 计算树枝的总和？

How to calculate sum of tree branches using Python?

binary-tree

python-3.x