我已经从排序数组创建了一个平衡的BST,我的问题是如何测试它简单地测试一棵树是否平衡是没有帮助的,因为即使是二叉树(注意提到的二叉树,不是BST)也可以平衡。测试树是否为BST也不是enof我现在唯一的答案是检查它是否balanced' &&
bst`现在这是一个复杂的两步测试过程。有没有更简单/更聪明的解决方案?
最佳答案
如果它是平衡的,那么它的深度最多为log(n)+1,其中n是树/数组中的节点数。
检查树是否确实是BST可以简单地通过“按顺序”遍历节点并确保它们确实是按顺序的来完成。
顺便说一句,如果你有一个排序数组,有一个非常简单的方法来构建一个平衡的bst,你运行的方式和在二进制搜索中一样-只使用“insert”和应用搜索的“both side”。例如,假设您有:
1,2,3,4,5,6,7,8,9
首先插入
5
,然后插入3
和7
,然后插入其余部分。