c - 二叉树 - 完成

Question

我目前正在学习 BST 并编写不同的函数，例如插入搜索。我遇到了一个有趣的编程面试问题，它要求编写一个函数来检查 bst 是否完整。

所以我的理解是，如果所有叶子都终止于同一层，则 BST 是完整的。

我对这个解决方案的可能的方法

我认为如果左右节点下的叶子终止于同一水平，则左右节点的高度应该相同。所以我可以做一个简单的检查，看看右子树的高度是否与左子树的高度相同，如果是，那么应该向我表明 BST 树是完整的。谁能确认我的方法是否正确或建议其他可能的方法？我不是在寻找代码，只是想研究我的理解和方法。

Answer 1

您的递归方法几乎是正确的。关于给定节点，您想询问的是以下问题:

• 左 child 是完整 BST 的根吗？如果是，它的高度是多少？
• 右 child 是否是完整 BST 的根，如果是，它的高度是否与左 child 的高度相同？

如果两者的答案都是肯定的，那么您就有了一个完整的 BST。

解决这个问题的另一种方法是回答以下关于树的三个问题。

• 它是 BST 吗？
• 其中有多少个节点？
• 它的高度是多少？

如果树是一个高度为 h 且有 2**h - 1 节点的二叉搜索树，那么你就有了一个完整的二叉搜索树。这三个问题中的每一个都可以用递归树遍历来回答。