0

我一直在努力解决递归问题，但我似乎无法弄清楚如何递归地退出函数/返回值。

给定整数值和目标值的二叉树，我试图找到并返回与目标值最接近的节点。

我能够遍历二叉树，并最终找到与目标匹配的节点，但是当我返回值时，它不会停止函数调用并返回匹配值，而是继续。最终，我似乎返回了初始节点和目标之间的差异，而不是正确的值。

任何人都可以阐明我该如何去做吗？

谢谢！

这是一项任务，这是我提交的答案。

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

2 回答 2

0

看看这些行：

    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 的唯一情况是当你到达一片叶子时。

这构成了一个问题。想象一棵有两根树枝的树。您的左分支将具有最接近的值，但您的右分支将具有目标。因为您不比较值并选择最接近目标的值，所以您将返回 valueL，即使 valueR 实际上可能更接近。

于 2020-05-03T13:27:57.997 回答
0

最简单的解决方案不需要围绕任何状态进行线程化：

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))]
    if candidates[0][1] == 0:
        return candidates[0]
    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))
于 2020-05-03T14:25:11.830 回答