Как рассчитать сумму ветвей деревьев с помощью 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

Вы можете использовать метод рекурсии, чтобы найти решение.

Ниже приведен код решения.Вы можете увидеть полный код здесь :

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()