在二叉树中查找与给定目标最接近的数字

Question

我有一个非常简单的二叉树

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

root = TreeNode(8)
root.left = TreeNode(5)
root.right = TreeNode(14)
root.left.left = TreeNode(4)
root.left.right = TreeNode(6)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.right = TreeNode(24)
root.right.right.left = TreeNode(22)

我实现了一个函数来查找树中离目标最近的数字（19）：

def closest_value(root, target, closest=0):
    if abs(root.val - target) < abs(closest - target):
        closest = root.val
        print(closest)
    if root.left is not None:
        closest_value(root.left, target, closest)
    if root.right is not None:
        closest_value(root.right, target, closest)
    return closest

结果显然应该是22，但我得到了8。令人惊讶的是，当我打印所有以下“最接近”的数字时，函数似乎工作正常：它打印：8、14、22。但为什么它不返回最新的clostest数字：22？

result = closest_value(root, 19)
print('result:', result)

Answer 1

您没有使用递归调用的结果来确定最终的返回值。

也许一个更简单的方法，不向下推默认参数会更容易：

def closest(node,value):
    if not node: return float('inf') 
    vals = [node.val, closest(node.left,value), closest(node.right,value)]
    return min(vals,key=lambda v:abs(v-value))

closest(root,19) # 22

一个问题是，这是一种O（n）方法，它将在不利用层次结构的情况下遍历整个二叉树。对于排序的二叉树，您可以通过实现一对二叉搜索函数来获得O（logN）解决方案，以找到值为

def findLE(node,value):
    if not node: return None
    if node.val == value: return node
    if node.val<value:    return findLE(node.right,value) or node
    return findLE(node.right,value)

def findGE(node,value):
    if not node: return None
    if node.val == value: return node
    if node.val>value:    return findGE(node.left,value) or node
    return findGE(node.right,value)

def closestValue(node,value):
    less = findLE(node,value)
    more = findGE(node,value)
    if more and less:
        return min(more.val,less.val,key=lambda v:abs(v-value))
    return (more or less).val

请注意，您的二叉树没有按排序顺序，因为节点 6 的剩余值为 8：

      8
   __/ \_
  5      14
 / \       \
4   6       24
   / \     /
  8   7  22

（您可以在此处找到二叉树打印功能。）

Answer 2

if语句中不更新第一次调用＜code＞closest_value＜/code＞时的closest值。只需将值赋给最接近的＜code＞即可：

def closest_value(root, target, closest=0):
    if abs(root.val - target) < abs(closest - target):
        closest = root.val
    if root.left is not None:
        #assign value
        closest = closest_value(root.left, target, closest)
    if root.right is not None:
        #assign value
        closest = closest_value(root.right, target, closest)
    return closest

result = closest_value(root, 19)
print(result)
# 22