Как вернуть значения рекурсивно

Question

Я пытался разобраться с рекурсией, но я не могу понять, как выйти из функции / вернуть значение рекурсивно.

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

Я могу пройти через двоичное дерево и в конечном итоге найти узел, который соответствует цели, однако, когда я возвращает значение, оно не останавливает вызовы функций и не возвращает совпадающее значение, но продолжается. В конце концов, мне кажется, что вместо правильных значений я возвращаю разницу между начальным узлом и целью.

Может ли кто-нибудь пролить свет на то, как я могу go сделать это?

Спасибо!

Это было задание, и это ответ, который я отправил.

class TreeNode:
"""
Reference based Binary Tree Node.
"""
def __init__(self, key, data, leftPtr = None, rightPtr = None):
    """
    [key] and [data] are expected.
    """
    self.key = key
    self.data = data
    self.leftT = leftPtr
    self.rightT = rightPtr

def toString(self):
    return "[K:%d|D%s | left at %d |right at %d]"%(self.key, self.data, self.leftT, self.rightT)

class BTSimple:
    """
    Simplified BT implemented with reference
    """
    def __init__(self, vList):
        """
        Construct a BT base on the [vList]
        vList has the format [root, [Left Tree], [Right Tree]], 
            where left and right tree has the same format
        """
        self._root = self._buildBT(vList)
        self._size = len(vList)

def _buildBT(self, vList):

    if vList == []:
        return None

    t = TreeNode(vList[0], str(vList[0]))

    if len(vList) > 1:
        t.leftT = self._buildBT(vList[1])
        t.rightT = self._buildBT(vList[2])

    return t

def _spaces(level):
    """
    Internal helper method to generate 4 spaces per level.
    """
    return ' '*(level*4)

def _pPrintRecursive(self, T, level):
    """
    Internal helper method to do "pretty" printing of AVL Tree.
    """
    if T == None:
        return

    self._pPrintRecursive(T.rightT, level+1)

    print(BTSimple._spaces(level), end='')
    print(T.key, end='')
    if T.leftT != None or T.rightT != None:
        print("---")
    else:
        print()
    self._pPrintRecursive(T.leftT, level+1)

def prettyPrint(self):
    """
    Print the Binary Tree in more visual way. 
    """
    self._pPrintRecursive(self._root, 0)


def _closestR(self,tree,target,closest = 9999):

    if tree is None:
        print("Tree is none, returning....")
        return
    print("Initialising _closestR..")
    print ("Current treenode is " + str(tree.data) + ", with the target being " + str(target))
    #Search for the exact match first
    #If no exact match, find closest
    #Use pre-order traversal
    distance = abs(target - tree.key)
    if distance < closest:
        closest = distance

    if distance == 0:
        return tree.key
    print("before traversing left, distance is " + str(distance) + " and closest is " + str(closest))
    valueL = self._closestR(tree.leftT,target,closest)
    if valueL is not None:
        print(valueL)
        return valueL
    else:
        print("None returned. Tree is : " + str(tree.key))
    valueR = self._closestR(tree.rightT,target,closest)
    if valueR is not None:
        print(valueR)
        return valueR

    return closest

def closestRecursive(self, target):
    """ This is just a wrapper to call the actual function """

    return self._closestR(self._root,target) 






def main():

#BTSimple construct a tree from a list with the format
# [root, [Left Tree], [Right Tree]], where left and right tree has the same format

bt = BTSimple([6, [2, [-14], []], [8, [13, [11], []], [16, [15], [-18, [-9], []]]]]) 
bt.prettyPrint()

print("Closest to %d is node %d\n"%(11, bt.closestRecursive(11)))
print("Closest to %d is node %d\n"%(-14, bt.closestRecursive(-14)))

print("Closest to %d is node %d\n"%(-15, bt.closestRecursive(-15)))
print("Closest to %d is node %d\n"%(-3, bt.closestRecursive(-3)))
print("Closest to %d is node %d\n"%(20, bt.closestRecursive(20)))
print("Closest to %d is node %d\n"%(-22, bt.closestRecursive(-22)))

print("Closest to %d is node %d\n"%(12, bt.closestRecursive(12)))  





if __name__ == "__main__":
    main()

Answer 1

Самое простое решение не требует многопоточности какого-либо состояния:

def closest1(self, target):
    candidates = [self.key]
    if self.leftT:
        candidates.append(self.leftT.closest1(target))
    if self.rightT:
        candidates.append(self.rightT.closest1(target))
    return min(candidates, key=lambda x: abs(x - target))

Недостатком является пересчет ключа локально ближайшего значения на каждом уровне рекурсии. Это можно исправить, возвращая как значение, так и его расстояние.

def _closest_helper(self, target):
    candidates = [(self.key, abs(self.key - target))]
    if self.leftT:
        candidates.append(self.leftT._closest_helper(target))
    if self.rightT:
        candidates.append(self.rightT._closest_helper(target))
    return min(candidates, key=lambda x: x[1])

def closest2(self, target):
    return self._closest_helper()[0]

Поскольку дерево неупорядочено, единственная оптимизация, которую вы можете сделать, - это немедленно вернуться к совпадению точного :

def _closest_helper(self, target):
    candidates = [(self.key, abs(self.key - target))]
    <b>if candidates[0][1] == 0:
        return candidates[0]</b>
    if self.leftT:
        candidates.append(self.leftT._closest_helper(target))
    if self.rightT:
        candidates.append(self.rightT._closest_helper(target))
    return min(candidates, key=lambda x: x[1])

Поскольку дерево неупорядочено, концептуально все, что вы делаете, - это собираете все ключи, а затем определяете, какой из них ближе всего. Вы можете сделать это с помощью универсального итератора

# left-to-right, pre-order traversal
def __iter__(self):
    yield self.key
    if self.leftT:
        yield from self.leftT
    if self.rightT:
        yield from self.rightT

Затем примените min, как для любой итерируемой:

def closest(self, target):
    return min(self, key=lambda x: abs(x - target))

Answer 2

Взгляните на эти строки:

    if distance == 0:
        return tree.key
    print("before traversing left, distance is " + str(distance) + " and closest is " + str(closest))
    valueL = self._closestR(tree.leftT,target,closest)
    if valueL is not None:
        print(valueL)
        return valueL
    else:
        print("None returned. Tree is : " + str(tree.key))
    valueR = self._closestR(tree.rightT,target,closest)
    if valueR is not None:
        print(valueR)
        return valueR

Единственный случай, когда вы возвращаете None, - это когда вы достигаете листа.

Это создает проблему. Изобразите дерево с двумя ветвями. Ваша левая ветвь будет иметь ближайшее значение, но ваша правая ветвь будет иметь цель. Поскольку вы не сравниваете значения и не выбираете ближайший к цели, вы вернете значение L, даже если значение R может быть ближе.