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

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。令人惊讶的是，当我打印以下所有 'closest' 数字时，函数似乎工作正常：它打印：8、14、22。但是为什么return最新最接近的号码：22？

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

Answer 1

第一次调用 closest_value 时 closest 的值没有在 if 语句中更新。只需将值分配给 closest:

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

Answer 2

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

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

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) 解决方案，方法是实现一对二分搜索函数以找到值 <= 的最近节点和值 >= 的最近节点。然后只应用将在 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

(可以找到二叉树打印函数here)

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

Finding the closest number in a Binary Tree to a given target

python

binary-tree

closest