二叉树的面试题总结

2017-07-22 17:55 阅读 369 次 评论 0 条

前面博客已经实现了大部分关于二叉树的面试题,本篇主要针对几个稍有难度的题型展开分析,对前面已经提过或本身难度较低的只做简单的分析。

二叉树面试题集锦

下列列表中未实现的,查看二叉树的基本操作及部分面试题,本文主要针对有一定难度的面试题分析。

7.二叉树的最近公共祖先结点

最近公共祖先存在以下两种情况:

二叉树是从上向下遍历,既然要求最近的公共祖先结点,我们需要借助具有先进后出的栈来实现,分别通过两个栈保存两个节点经过的路径,这就转化成类似于两个链表求交点的问题。

比如上图中:A)求节点①与节点③的最近公共祖先,那么stack1与stack2分别保存遍历到①和③的路径:

此时,我们让栈内节点多的出栈,直到两个栈节点个数一致,然后一起出栈,直到栈顶节点的值相等即为祖先结点。

B)同理,节点④和⑤不处于同一条直线时,两个栈保存的路径如下:

此时,与A)的求解方法一致,转化成了链表相交问题一样。

8.判断是否为平衡二叉树

借助后序遍历思想,在遍历过程中更新子树高度,判断是否满足AVL树(左右子树高度的绝对值小于1)的性质,有效避免了重复遍历,时间复杂度为O(n)。

9.二叉树中最远两个节点之间的距离

距离最远的两个节点存在两种情况:① 经过根节点 ②未经过根节点,在根的某个子树上。那么有以下结论:

我们可以借助后序遍历的思想,对于每一个节点先获得左子树与右子树的深度,然后引入一个distance与之比较,大于distance时更新distance 的值。

11.判断是否为完全二叉树

借助层序遍历的思想,底层使用队列来实现。遍历二叉树时,如果遇到第一个空节点且该树已经遍历至末尾,则这棵树是完全二叉树。如果遇到空节点且后面还存在节点,则不是完全二叉树。

我们利用一个标志位flag,默认为false,当遇到第一个空节点时,将其置为true,true之后存在节点为假,true之后不存在节点为真。

10.前序+中序重建二叉树

另外一篇博客:重建二叉树,有详细的解析。

13.将二叉搜索树转换为双向链表

另外一篇博客:二叉搜索树转双向链表 ,在此不再獒述。

14.树的子树

子树问题不同于子结构,它描述的是一棵树从根到叶子结点完全相同,子树一定是子结构,但子结构不一定是子树,如下图所示:

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:二叉树的面试题总结 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情