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

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

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

为了解决这个问题，我们可以遵循一种有效的方法。由于一个节点的所有后代都小于或大于它，那么我们可以遵循以下步骤：

  • 获取节点的下一个先序后继

  • 获取节点的最后一个先序后继

  • 现在，当两个后继都小于或大于当前节点时，再次检查，否则返回false。

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

  • next := 0, last := 0
  • 对于范围从0到preorder大小减1的i，执行：
    • next := preorder[i] - preorder[i+1]
    • last := preorder[i] - preorder的最后一个值
    • 如果 next * 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))

输入

[22, 12, 13, 15, 14]

输出

True

更新于：2020-12-30

257 次浏览

开启您的职业生涯

完成课程获得认证

开始
广告