转一些我blog上一些常见的二叉树面试问题和总结 - 未名空间MITBBS历史存档

转一些我blog上一些常见的二叉树面试问题和总结# JobHunting - 待字闺中

i*e2010-09-18 07:09

1 楼

二叉树是面试里常见的问题种类，大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌握好。
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)有两
种，面试者必须对这题熟悉。
Binary Search Tree In-Order Traversal Iterative Solution
这题应该是 google 电面经常问的问题吧。我那时候就是google电面没答好这问题，所
以就fail了，超级后悔啊。强烈推荐的问题。In-Order traversal能很轻松地用递

A*r2010-09-18 07:09

2 楼

不错，正在复习这一块。。
谢谢分享和总结。。

集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left

【在 i**********e 的大作中提到】

: 二叉树是面试里常见的问题种类，大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌握好。
: 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)有两
: 种，面试者必须对这题熟悉。
: Binary Search Tree In-Order Traversal Iterative Solution
: 这题应该是 google 电面经常问的问题吧。我那时候就是google电面没答好这问题，所
: 以就fail了，超级后悔啊。强烈推荐的问题。In-Order traversal能很轻松地用递

i*e2010-09-18 07:09

3 楼

Your idea is correct, using two stacks can solve this question easily. However, there are few bugs in your program. Consider the tree below:
3
/ \
9 20
/ \
15 7
PrintTreeLevelZigZag should print 3 20 9 15 7
the rightToLeft order should be changed when it reaches the end of each
level. In your case, you change the order after each iteration.
Another case you want to consider is what if newNode is NULL? you forgot
to check it. This will crash your program.

from

n*g2010-09-18 07:09

4 楼

你说的第一条我post帖子后就发现了，第二条我没有注意到。多谢指正！下面是新的
code。好像两个连续的一样的while有点怪，可以把外面的转为do while。
void PrintTreeLevelZigZag(Node* root)
{
Stack *currentStack = new Stack();
Stack *nextStack = new Stack();
Stack *tempStack;
bool bLeftToRight = true;//the print order of the current level is from
left to right if it is true.
Node *newNode;
if(root)
currentStack->Push(root);
while(currentStack->Peek() != NULL)
{
while(currentStack->Peek() != NULL)
{

【在 i**********e 的大作中提到】

: Your idea is correct, using two stacks can solve this question easily. However, there are few bugs in your program. Consider the tree below:
: 3
: / \
: 9 20
: / \
: 15 7
: PrintTreeLevelZigZag should print 3 20 9 15 7
: the rightToLeft order should be changed when it reaches the end of each
: level. In your case, you change the order after each iteration.
: Another case you want to consider is what if newNode is NULL? you forgot

w*e2010-09-18 07:09

5 楼

多谢楼主分享。

i*e2010-09-18 07:09

6 楼

还有一个小bug呢。
一开始我也没看到，但是把你程序执行一下就crash了。
问题就出在这行代码：
while(currentStack->top() != NULL)

from

【在 n*****g 的大作中提到】

: 你说的第一条我post帖子后就发现了，第二条我没有注意到。多谢指正！下面是新的
: code。好像两个连续的一样的while有点怪，可以把外面的转为do while。
: void PrintTreeLevelZigZag(Node* root)
: {
: Stack *currentStack = new Stack();
: Stack *nextStack = new Stack();
: Stack *tempStack;
: bool bLeftToRight = true;//the print order of the current level is from
: left to right if it is true.
: Node *newNode;

s*t2010-09-18 07:09

7 楼

常看楼主博客，收获很大，谢谢！

集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left

【在 i**********e 的大作中提到】

: 二叉树是面试里常见的问题种类，大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌握好。
: 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)有两
: 种，面试者必须对这题熟悉。
: Binary Search Tree In-Order Traversal Iterative Solution
: 这题应该是 google 电面经常问的问题吧。我那时候就是google电面没答好这问题，所
: 以就fail了，超级后悔啊。强烈推荐的问题。In-Order traversal能很轻松地用递

i*e2010-09-18 07:09

8 楼

谢啦，希望你常来 :)

【在 s*******t 的大作中提到】

: 常看楼主博客，收获很大，谢谢！
:
: 集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
: 握好。
: left

i*e2010-09-18 07:09

9 楼

nicheng,
你的currentStack->peek()是什么意思呀？
peek()是询问最top element的意思吗？

from

【在 n*****g 的大作中提到】

: 你说的第一条我post帖子后就发现了，第二条我没有注意到。多谢指正！下面是新的
: code。好像两个连续的一样的while有点怪，可以把外面的转为do while。
: void PrintTreeLevelZigZag(Node* root)
: {
: Stack *currentStack = new Stack();
: Stack *nextStack = new Stack();
: Stack *tempStack;
: bool bLeftToRight = true;//the print order of the current level is from
: left to right if it is true.
: Node *newNode;

g*d2010-09-18 07:09

10 楼

好像不用这么复杂.
push完一层后压一个left or right dummy node.下一层根据这个dummy决定从左到右,
或从右到左. 再push一个反方向的dummy node.

from

【在 n*****g 的大作中提到】

: 你说的第一条我post帖子后就发现了，第二条我没有注意到。多谢指正！下面是新的
: code。好像两个连续的一样的while有点怪，可以把外面的转为do while。
: void PrintTreeLevelZigZag(Node* root)
: {
: Stack *currentStack = new Stack();
: Stack *nextStack = new Stack();
: Stack *tempStack;
: bool bLeftToRight = true;//the print order of the current level is from
: left to right if it is true.
: Node *newNode;

n*g2010-09-18 07:09

11 楼

ihasleetcode, 抱歉没有来得及回你的帖子！是的，peek（）的意思是返回top
element，如果不存在应该返回null。我还没有run 这个code，晚上我来run一下看是不
是会crash。

【在 i**********e 的大作中提到】

: nicheng,
: 你的currentStack->peek()是什么意思呀？
: peek()是询问最top element的意思吗？
:
: from

s*12010-09-18 07:09

12 楼

总结的好

b*r2010-09-18 07:09

13 楼

lz没说zig-zag traverse不能recersive吧
我的java code, run过了
public static void zigZagTraverse(BinaryTreeNode root){
if (root == null) return;
Stack curStack = new Stack();
curStack.push(root);
zigZag(curStack, true);
}

public static void zigZag( Stack nodes, boolean
leftThenRight ){
Stack s = new Stack();
while ( !nodes.isEmpty() ){
BinaryTreeNode node = nodes.pop();
System.out.println(node.data);
if ( leftThenRight ){
if ( node.left != null )
s.push(node.left);
if ( node.right != null )
s.push(node.right);
}
else{
if ( node.right != null )
s.push(node.right);
if ( node.left != null )
s.push(node.left);
}
}
if ( s.size() > 0 ){
zigZag(s, (!leftThenRight));
}
return;
}

b*r2010-09-18 07:09

14 楼

请问这个是什么意思没看懂 next right到底是指向谁
Populating Next Right Pointers in Each Node
这题就是把所有node的next right指针指向右边邻居。如果没有邻居，应该指向null。

i*e2010-09-18 07:09

15 楼

This is the original question from my blog:
Given a binary tree
struct Node {
Node* leftChild;
Node* rightChild;
Node* nextRight;
}
Populate the nextRight pointers in each node.
Your task is to initialize all nextRight pointers such that it points to its
right neighbor.

【在 b********r 的大作中提到】

: 请问这个是什么意思没看懂 next right到底是指向谁
: Populating Next Right Pointers in Each Node
: 这题就是把所有node的next right指针指向右边邻居。如果没有邻居，应该指向null。

b*r2010-09-18 07:09

16 楼

请问你的blog在哪里啊 thanks!!!
right neighbor就是同一个level里右边的那个node对吧
比如下面这个树
1
2 3
6 7 9 11
1,3和11没有nextRight
2的nextRight是3
6是7， 7是9， 9是11?
貌似是BFT的变种?

its

【在 i**********e 的大作中提到】

: This is the original question from my blog:
: Given a binary tree
: struct Node {
: Node* leftChild;
: Node* rightChild;
: Node* nextRight;
: }
: Populate the nextRight pointers in each node.
: Your task is to initialize all nextRight pointers such that it points to its
: right neighbor.

b*r2010-09-18 07:09

17 楼

google了一下这个是你的blog?
http://www.ihas1337code.com/2010/03/first-on-site-technical-interview.html

i*e2010-09-18 07:09

18 楼

对的。
如果没有右邻应该指向null。
可以用BFT来解，但是BFT需要额外空间。

【在 b********r 的大作中提到】

: 请问你的blog在哪里啊 thanks!!!
: right neighbor就是同一个level里右边的那个node对吧
: 比如下面这个树
: 1
: 2 3
: 6 7 9 11
: 1,3和11没有nextRight
: 2的nextRight是3
: 6是7， 7是9， 9是11?
: 貌似是BFT的变种?

b*r2010-09-18 07:09

19 楼

bft的确不是最好的看了你的blog 很有帮助谢谢!

【在 i**********e 的大作中提到】

: 对的。
: 如果没有右邻应该指向null。
: 可以用BFT来解，但是BFT需要额外空间。

c*n2010-09-18 07:09

20 楼

Thanks

h*32010-09-18 07:09

21 楼

请问能否share
Binary Search Tree In Order Iterative Traversal without using a visited flag
的方法?

集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left

【在 i**********e 的大作中提到】

: 二叉树是面试里常见的问题种类，大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌握好。
: 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)有两
: 种，面试者必须对这题熟悉。
: Binary Search Tree In-Order Traversal Iterative Solution
: 这题应该是 google 电面经常问的问题吧。我那时候就是google电面没答好这问题，所
: 以就fail了，超级后悔啊。强烈推荐的问题。In-Order traversal能很轻松地用递

p*72010-09-18 07:09

22 楼

给楼主补充几个题吧
BST转为双链表
双链表转为平衡BST
求leaf之间最大距离
由inorder和preorder的序列，重建BST

i*e2010-09-18 07:09

23 楼

不用visited flag也可以实现，就是利用一个current pointer加上一个stack。
首先把current初始化为Root，然后一直往左走，当中把经过的node都push上stack里。
碰到null了，就从stack里pop一个出来指向current，打印current的值，然后把
current指向右孩子，然后重复以上的步骤。
当stack里是空的，也就意识着已经打印完毕。
http://www.ihas1337code.com/2010/04/binary-search-tree-in-order-traversal.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

flag

【在 h******3 的大作中提到】

: 请问能否share
: Binary Search Tree In Order Iterative Traversal without using a visited flag
: 的方法?
:
: 集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
: 握好。
: left

i*e2010-09-18 07:09

24 楼

leaf 之间最大的距离？不是很懂。leaf之间必须是同一个level的吗？如果不是同一个
level的应该怎样？
我知道preorder序列能重建BST。但inorder序列不能重建原来的那个BST吧。是不是
inorder序列建一个平衡的BST？
感谢你的补充题，我会研究研究下。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 p********7 的大作中提到】

: 给楼主补充几个题吧
: BST转为双链表
: 双链表转为平衡BST
: 求leaf之间最大距离
: 由inorder和preorder的序列，重建BST

n*n2010-09-18 07:09

25 楼

what is "right neighbor" in ur problem?

【在 b********r 的大作中提到】

: 请问这个是什么意思没看懂 next right到底是指向谁
: Populating Next Right Pointers in Each Node
: 这题就是把所有node的next right指针指向右边邻居。如果没有邻居，应该指向null。

i*e2010-09-18 07:09

26 楼

比如下面这个树
1
2 3
6 7 9 11
1,3和11没有nextRight
2的nextRight是3
6是7， 7是9， 9是11.
注：没有nextRight应该把nextRight指向NULL.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 n******n 的大作中提到】

: what is "right neighbor" in ur problem?

n*n2010-09-18 07:09

27 楼

如果把9去掉，7的right是11还是nil？

【在 i**********e 的大作中提到】

: 比如下面这个树
: 1
: 2 3
: 6 7 9 11
: 1,3和11没有nextRight
: 2的nextRight是3
: 6是7， 7是9， 9是11.
: 注：没有nextRight应该把nextRight指向NULL.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*e2010-09-18 07:09

28 楼

这样的话是nil。
原题是你可以assume是full binary tree。

【在 n******n 的大作中提到】

: 如果把9去掉，7的right是11还是nil？

p*72010-09-18 07:09

29 楼

需要inorder和preorder 两个序列才能重构
leaf 之间是任意的，可以说是任意节点之间的距离

【在 i**********e 的大作中提到】

: leaf 之间最大的距离？不是很懂。leaf之间必须是同一个level的吗？如果不是同一个
: level的应该怎样？
: 我知道preorder序列能重建BST。但inorder序列不能重建原来的那个BST吧。是不是
: inorder序列建一个平衡的BST？
: 感谢你的补充题，我会研究研究下。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

K*g2010-09-18 07:09

30 楼

用一个queue+stack也可以实现
其实用queue就是那种标准的level-order遍历的方法，再加个stack就可以zig-zag了

from

【在 n*****g 的大作中提到】

: 你说的第一条我post帖子后就发现了，第二条我没有注意到。多谢指正！下面是新的
: code。好像两个连续的一样的while有点怪，可以把外面的转为do while。
: void PrintTreeLevelZigZag(Node* root)
: {
: Stack *currentStack = new Stack();
: Stack *nextStack = new Stack();
: Stack *tempStack;
: bool bLeftToRight = true;//the print order of the current level is from
: left to right if it is true.
: Node *newNode;

s*a2010-09-18 07:09

31 楼

Thanks.

集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left

【在 i**********e 的大作中提到】

: 二叉树是面试里常见的问题种类，大家在面试前必须熟悉这一类的问题。以下是我收集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌握好。
: 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)有两
: 种，面试者必须对这题熟悉。
: Binary Search Tree In-Order Traversal Iterative Solution
: 这题应该是 google 电面经常问的问题吧。我那时候就是google电面没答好这问题，所
: 以就fail了，超级后悔啊。强烈推荐的问题。In-Order traversal能很轻松地用递

i*e2010-09-18 07:09

32 楼

更新：
Finding the Maximum Height of a Binary Tree
这题就是寻找二叉树的最深度，利用DFS可以轻松解决。挑战的是：如何写非递归的版
本。有两种解法，一是用BFS，解法比较直接。另一种解法是转换成非递归BFS，方法请
参考In-Order Traversal Iterative Solution.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

i*e2010-09-18 07:09

33 楼

更新：
添加了两道新题，请参考第一页：
Serialization/Deserialization of Binary Tree
Rebuild Binary Search Tree from Pre-order Traversal
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

K*n2010-09-18 07:09

34 楼

GOOD, thanks

i*e2010-09-18 07:09

35 楼

怎么可以用一个queue+stack来打印zig-zag呢？
例如：以下这个例子，怎么打印 0, 1, 2, 3, ..., 14?
___ 0___
/ \
1 2
/ \ / \
6 5 4 3
/ \ / \ / \ / \
7 8 9 10 11 12 13 14
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 K******g 的大作中提到】

: 用一个queue+stack也可以实现
: 其实用queue就是那种标准的level-order遍历的方法，再加个stack就可以zig-zag了
:
: from

i*e2010-09-18 07:09

36 楼

Print Edge Nodes (Boundary) of a Binary Tree
问题是要把树的周围counter-clockwise打印出来。先打印root，然后从上到下打印最
左边的节点，然后从左到右的顺序打印叶子节点，然后从下到上打印最右边的节点。这
题的精粹就在于使用depth-first traversal，一个递归就能搞定。先把树分为两个树
（root的左孩子和右孩子）处理。先处理左树，再处理右树。如果卡在怎么从下到上打
印最右边节点，可以想想post-order traversal。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

i*e2010-09-18 07:09

37 楼

更新，加了一道新问题总结：
Binary Tree Post-Order Traversal Iterative Solution
这题比起 In-Order Traversal 难多了。是很罕见的面试题，好像只有 amazon 问过这
道题。用 visited flags 好做很多，但是不用 visited flags 还是有可能解出来的。
思路就是利用一个变量储存之前访问的节点。然后在每次循环的时候比较之前节点和
stack 上的节点，这样就可以知道我们在往上还是往下走。如果往上走的话，就能得知
是从左节点还是右节点上来的，这有大大的帮助。另外一个方法是使用两个 stack，解
法很简洁，很巧妙，但是空间复杂度没有一个 stack 的解法少。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

s*n2010-09-18 07:09

38 楼

不能都放在一个stack里面，最后向外push吗？

【在 i**********e 的大作中提到】

: 更新，加了一道新问题总结：
: Binary Tree Post-Order Traversal Iterative Solution
: 这题比起 In-Order Traversal 难多了。是很罕见的面试题，好像只有 amazon 问过这
: 道题。用 visited flags 好做很多，但是不用 visited flags 还是有可能解出来的。
: 思路就是利用一个变量储存之前访问的节点。然后在每次循环的时候比较之前节点和
: stack 上的节点，这样就可以知道我们在往上还是往下走。如果往上走的话，就能得知
: 是从左节点还是右节点上来的，这有大大的帮助。另外一个方法是使用两个 stack，解
: 法很简洁，很巧妙，但是空间复杂度没有一个 stack 的解法少。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*e2010-09-18 07:09

39 楼

你可以试试，这道题没那么直接。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 s*****n 的大作中提到】

: 不能都放在一个stack里面，最后向外push吗？

n*p2010-09-18 07:09

40 楼

mark~~~~~~~~~~

i*e2010-09-18 07:09

41 楼

更新，一道新面试题总结：
Largest BST in a Binary Tree
要求在树里找最大的 BST subtree。注意，这里指的是 subtree，如果不清楚定义，先
跟面试官确定一下。subtree 在维基百科的定义是指包括树节点和它所有的
descendents。做这题前必须知道怎么才能判断树是不是 BST。这题的巧妙之处在于利
用了 bottom-up 的 Depth-first 遍历来解决所有 top-down 遍历的难处。当然，如果
面试官要求的是 largest BST（不一定是 subtree），那就是另外一套思路了。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

j*y2010-09-18 07:09

42 楼

看天书的飘过，崇拜一下楼主。

l*32010-09-18 07:09

43 楼

inorder遍历树，同时找longest increasing sequence?

【在 i**********e 的大作中提到】

: 更新，一道新面试题总结：
: Largest BST in a Binary Tree
: 要求在树里找最大的 BST subtree。注意，这里指的是 subtree，如果不清楚定义，先
: 跟面试官确定一下。subtree 在维基百科的定义是指包括树节点和它所有的
: descendents。做这题前必须知道怎么才能判断树是不是 BST。这题的巧妙之处在于利
: 用了 bottom-up 的 Depth-first 遍历来解决所有 top-down 遍历的难处。当然，如果
: 面试官要求的是 largest BST（不一定是 subtree），那就是另外一套思路了。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*e2010-09-18 07:09

44 楼

这是个比较容易掉入的误区。
你可以尝试找找反例。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 l**********3 的大作中提到】

: inorder遍历树，同时找longest increasing sequence?

j*a2010-09-18 07:09

45 楼

will this work?
void f(NODE* r)
{
// define stack1, stack2;
stack1.push(r);
while(!stack1.empty && !stack2.empty)
{
while(!stack1.empty)
{
NODE* n=stack1.pop();
if(n->r) stack2.push(n->r);
if(n->l) stack2.push(n->l);
}
while(!stack2.empty)
{
NODE* n=stack2.pop();
if(n->l) stack1.push(n->l);
if(n->r) stack1.push(n->r);
}
}
}

i*e2010-09-18 07:09

46 楼

longest increasing sequence 的方法来找最大的 BST（不管是 subtree 与否）是个
容易掉入的误区。
你可以参考一下我贴的图片，这就是其中的反例之一.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 l**********3 的大作中提到】

: inorder遍历树，同时找longest increasing sequence?

i*e2010-09-18 07:09

47 楼

Could you please explain the idea of your code?
I am not quite sure of your idea.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 j*******a 的大作中提到】

: will this work?
: void f(NODE* r)
: {
: // define stack1, stack2;
: stack1.push(r);
: while(!stack1.empty && !stack2.empty)
: {
: while(!stack1.empty)
: {
: NODE* n=stack1.pop();

z*t2010-09-18 07:09

48 楼

顶，过几天再仔细看看