i**********e 发帖数: 1145 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: ihasleetcode (1337coder), 信区: JobHunting
标 题: 转一些我blog上一些常见的二叉树面试问题和总结
发信站: BBS 未名空间站 (Sat Sep 18 22:32:55 2010, 美东)
二叉树是面试里常见的问题种类,大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题(包括我亲身经历的)。多做多练习,相信你一定可以掌握好。
Determine if a Binary Tree is a Binary Search Tree
这题很常见,microsoft,amazon, google的面试都有人被问过。这题也是二叉树的好题
,必须得对BST的定义搞清楚。有一个常见的陷阱,就是把current node的value和left
node, right node比较;这是不正确的解法。也有一个很容易想到的brute force解法
,但是每个node会被遍历很多次。正确的优解是 (O(N)解,N=number of nodes)有两
种,面试者必须对这题熟悉。 | S*******w 发帖数: 24236 | 2 赞。
集的一些常见二叉树面试问题(包括我亲身经历的)。多做多练习,相信你一定可以掌
握好。
left
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: ihasleetcode (1337coder), 信区: JobHunting : 标 题: 转一些我blog上一些常见的二叉树面试问题和总结 : 发信站: BBS 未名空间站 (Sat Sep 18 22:32:55 2010, 美东) : 二叉树是面试里常见的问题种类,大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题(包括我亲身经历的)。多做多练习,相信你一定可以掌握好。 : Determine if a Binary Tree is a Binary Search Tree : 这题很常见,microsoft,amazon, google的面试都有人被问过。这题也是二叉树的好题 : ,必须得对BST的定义搞清楚。有一个常见的陷阱,就是把current node的value和left : node, right node比较;这是不正确的解法。也有一个很容易想到的brute force解法 : ,但是每个node会被遍历很多次。正确的优解是 (O(N)解,N=number of nodes)有两
| i**********e 发帖数: 1145 | 3 更新:
Finding the Maximum Height of a Binary Tree
添加了两道新题,请参考第一页:
Serialization/Deserialization of Binary Tree
Rebuild Binary Search Tree from Pre-order Traversal
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | i**********e 发帖数: 1145 | 4 更新,加了一道新问题总结:
Binary Tree Post-Order Traversal Iterative Solution
这题比起 In-Order Traversal 难多了。是很罕见的面试题,好像只有 amazon 问过这
道题。用 visited flags 好做很多,但是不用 visited flags 还是有可能解出来的。
思路就是利用一个变量储存之前访问的节点。然后在每次循环的时候比较之前节点和
stack 上的节点,这样就可以知道我们在往上还是往下走。如果往上走的话,就能得知
是从左节点还是右节点上来的,这有大大的帮助。另外一个方法是使用两个 stack,解
法很简洁,很巧妙,但是空间复杂度没有一个 stack 的解法少。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | h**********8 发帖数: 267 | | h**********8 发帖数: 267 | |
|