python - 在二叉搜索树中查找地板和天花板

Question

我一直在努力解决一个代码问题，我必须在二叉搜索树中找到给定数字的下限和上限。例如，给出了 5，所以程序应该打印 4 表示地板，6 表示天花板（如果它们存在）。否则，它应该为它们中的每一个打印 None 。

这是一个示例代码来解释：

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

def findCeilingFloor(root_node, k, floor=None, ceil=None):
    # Fill this in.

root = Node(8) 
root.left = Node(4) 
root.right = Node(12) 

root.left.left = Node(2) 
root.left.right = Node(6) 

root.right.left = Node(10) 
root.right.right = Node(14) 

print findCeilingFloor(root, 5)
# (4, 6)

我为 findCeilingFloor 函数实现了一些代码。尽管它找到并分配了下限和上限值，但当程序返回到包含 12 作为值的节点时，它再次将下限和上限值更改为无。因此，它总是为它们返回 None 。我添加了一些打印语句来跟踪正在发生的事情。

这是我的输出：

问题输出

这是我的实现：

def findCeilingFloor(root_node, k, floor=None, ceil=None):
    # Fill this in.
    print(f"Current node value = {root_node.value}")
    print(f"Floor value = {floor}")
    print(f"Ceil value = {ceil}")
    print()

    if root_node.value == k - 1:
        floor = root_node.value

    if root_node.value == k + 1:
        ceil = root_node.value

    if root_node.left:
        findCeilingFloor(root_node.left, k, floor, ceil)

    if root_node.right:
        findCeilingFloor(root_node.right, k, floor, ceil)

    return floor, ceil

我不明白为什么我的代码对它们都返回 None 即使它找到了 floor 和 ceil 值（ceil 值没有出现在输出中，因为它在分配 ceil 之前打印，我检查了是否它也找到了 ceil）。当左子树上没有节点可走时，它指向右子树，指向 12，然后 floor 和 ceil 都变为 None。

标签： pythonooprecursionbinary-treebinary-search-tree

Answer 1

您的代码存在一个主要问题。

将参数传递给函数并不像你想象的那样工作

看下面的代码并尝试猜测输出，然后与实际输出进行比较：

def f(x):
  g(x)
  return x

def g(x):
  x = 3

print(f(4))

那么，是输出3，还是4？自己试试。事实证明，函数g不会修改f变量x。x = 3主体中的语句g分配了一个名为的局部变量x，该变量与f's 不同。

修复代码

def findCeilingFloor(root_node, k):
    # Fill this in.
    print(f"Current node value = {root_node.value}")
    print(f"Floor value = {floor}")
    print(f"Ceil value = {ceil}")
    print()

    floor, ceil = None, None

    if root_node.value == k - 1:
        floor = root_node.value
    elif root_node.left:
        floor = findCeilingFloor(root_node.left, k, floor, ceil)

    if root_node.value == k + 1:
        ceil = root_node.value
    elif root_node.right:
        ceil = findCeilingFloor(root_node.right, k, floor, ceil)

    return floor, ceil

另一个问题： floor 和 ceil 的含义

很可能还有另一个问题。您可能误解了“地板”和“天花板”应该是什么。你确定那些指的是价值观k-1吗k+1？您正在寻找的可能是对于 floor小于ktree中的最大值，对于 ceil是大于tree 中的最小值。k