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 的大作中提到】
: 【 以下文字转载自 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 | |
|
