Aar*_*ron 4 algorithm stack binary-search-tree data-structures
我正在将BST的递归函数转换为非递归函数以帮助准备面试.到目前为止,我想出了预订,订单,后序,搜索,删除,插入和转换BST到圆形链表.我无法弄清楚如何使用堆栈或队列来获取高度并找出它是否是BST.任何提示将非常感谢.我不是在寻找代码,而是寻找代码背后的逻辑.
对于初学者来说,为这样的面试做好准备!我希望你玩这些算法很开心.
让我们从尝试确定二叉树是否是BST的任务开始.执行此操作的一种方法是对树进行顺序遍历并检查元素是否按排序顺序排列.当且仅当树是BST时,这将是真实的.由于您已经有了对树的元素进行顺序遍历的代码,因此您应该能够轻松地调整代码以检查来自inorder walk的元素是否通过跟踪您在中看到的最后一个元素进行排序inorder walk,然后将生成的每个元素与前一个元素进行比较.如果两者乱序,则树不是BST.
要确定树的高度,一个选项是采取您到目前为止所提出的任何搜索(预订,后序,按顺序)并跟踪每个点的堆栈高度.这里的想法是,由于您的堆栈将始终跟踪从任何节点到根的路径,您可以简单地走树并记录您看到堆栈变得最深的.这个最大深度就是树的高度.
希望这可以帮助!和采访一起好运!