在 Python 中检查 BST 的每个内部节点是否只有一个子节点

pythonserver side programmingprogramming

假设我们有一个二叉搜索树 (BST) 的前序遍历。我们必须检查每个内部节点是否只有一个子节点。

因此，如果输入类似于 preorder = [22, 12, 13, 15, 14]，则输出将为 True，因为 BST 类似于 −

为了解决这个问题，我们可以采用一种有效的方法。由于节点的所有后代要么小于要么大于，那么我们可以按照以下步骤进行 −

获取节点的下一个前序后继
获取节点的最后一个前序后继
现在，当两个后继都小于或大于当前节点时，再次检查，否则返回 false。

为了解决这个问题，我们将遵循以下步骤 −

next := 0, last := 0
对于 i，范围从 0 到前序大小 - 1，执行
- next := preorder[i] - preorder[i+1]
- last := preorder[i] - 前序的最后一个值
- 如果下一个 * last < 0，然后
  - 返回 False
返回 True

让我们看看下面的实现，以便更好地理解 −

示例

def solve(preorder):
next = 0
last = 0
for i in range(len(preorder)-1):
next = preorder[i] - preorder[i+1]
last = preorder[i] - preorder[-1]
if next * last < 0:
return False
return True
preorder = [22, 12, 13, 15, 14] print(solve(preorder))