在 BST 中找到最接近的值

Question

为什么我收到一个错误，缺少 1 个必需的位置参数 root = findClosestValueInBst(8,)
类型错误：findClosestValueInBst() 缺少 1 个必需的位置参数：'target'

def findClosestValueInBst (tree, target):
  return findClosestValueInBstHelper(tree, target, float('inf'))

def findClosestValueInBstHelper(tree, target, closest):
  if tree is None:
    return closest
  if abs(target-closest) > abs(target - tree.value):
    closest = tree.value
  if target < tree.value:
    return findClosestValueInBstHelper(tree.left, target, closest)
  elif target > tree.value:
    return findClosestValueInBstHelper(tree.right, target, closest)
  else:
    return closest



root = findClosestValueInBst(8,)  
root.left = findClosestValueInBst(5)  
root.right = findClosestValueInBst(14) 
root.left.left = findClosestValueInBst(4)  
root.left.right = findClosestValueInBst(6) 
root.left.right.left = findClosestValueInBst(8)  
root.left.right.right = findClosestValueInBst(7)  
root.right.right = findClosestValueInBst(24) 
root.right.right.left = findClosestValueInBst(22)  
    
result = findClosestValueInBstHelper(root, 3)
print(result)

Answer 1

您定义了一个带有两个参数的函数：

def findClosestValueInBst (tree, target)

稍后您尝试仅使用一个参数调用它：

root = findClosestValueInBst(8,)

您看到的错误：

TypeError: findClosestValueInBst() missing 1 required positional argument: 'target'

告诉您它正在尝试调用该函数，但它不能，因为它不知道将名为 'target' 的参数设置为什么，因为您只传入了一个参数。

Answer 2

我看过你的代码，看来你首先需要通过添加节点来创建 BST。这可以通过以下步骤完成 -

首先创建一个TreeNode class，它有三个参数——value、left节点和right节点。
然后在您的辅助函数中，您需要检查哪个子树中存在最接近的值，即在左子树或右子树中。

这段代码应该会给你一个想法 -

class TreeNode:
  def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None


def findClosestValueInBST(tree, target):
  return findClosestValueInBstHelper(tree, target, tree.value)


def findClosestValueInBstHelper(tree, target, closest):
  # Base condition
  if tree is None:
    return closest
  if abs(target - closest) > abs(target - tree.value):
    closest = tree.value
  # If the target is present in the left subtree
  if target < tree.value:
    return findClosestValueInBstHelper(tree.left, target, closest)
  # If the target is present in the right subtree
  elif target > tree.value:
    return findClosestValueInBstHelper(tree.right, target, closest)
  else:
    return closest


# Here we are creating the BST
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)

closestValue = findClosestValueInBST(root, 3)
print("The closest value is: " + str(closestValue))

closestValue = findClosestValueInBST(root, 19)
print("The closest value is: " + str(closestValue))

希望对您有所帮助。编码愉快:)

在 BST 中找到最接近的值

Find Closest Value In BST

javascript

python

algorithm

data-structures

binary-search-tree