我目前正在学习BST并编写不同的函数,如insert search。我遇到一个有趣的编程面试问题,它要求编写一个函数来检查bst是否完成。
所以我的理解是,如果所有的叶子都在同一个层次上终止,那么BST是完整的。
我可能的解决方法
我想,如果右节点和左节点下的叶子在同一层终止,那么它们的高度应该是相同的。所以,我可以做一个简单的检查,看看右子树的高度是否与左子树的高度相同,如果是,那么这应该向我表明BST树是完整的。有人能确认我的方法是正确的还是建议其他可能的方法?我不是在寻找代码只是想工作在我的理解和方法。

最佳答案

你的递归方法几乎是正确的。对于给定的节点,您希望询问以下问题:
左子是一个完整的BST的根吗?如果是,它的高度是多少?
右边的孩子是一个完整的BST的根吗?如果是,它的高度和左边的孩子一样吗?
如果两者的答案都是肯定的,那么你就有一个完整的BST。
解决这个问题的另一种方法是回答下面关于树的三个问题。
是英国夏令时吗?
里面有多少个节点?
它的高度是多少?
如果树是具有h节点的高度2**h - 1的BST,那么就有一个完整的BST。这三个问题中的每一个都可以通过递归树遍历来回答。

关于c - 二叉树-完成,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/27139564/

10-11 23:04
查看更多