p*****2 发帖数: 21240 | 1 http://blog.sina.com.cn/s/blog_b9285de20101j4qt.html
一直没有总结Tree,这次想总结一下结果却发现没有什么太多可以总结的。Leetcode上
tree的题目还是比较全面的。我做了一遍发现基本上跑不出三个套路:
1. Recursive DFS
2. Iterative DFS
3. BFS
有些tree的题目比较tricky一些,但是最终解法还是逃不出这三个套路,所以我觉得面
试的时候代码的质量就变得更加的重要了。因为没有什么太多总结的,下边就随便聊一
下了。
Leetcode上graph的题目涉及的很少,不过从算法和coding来说DFS,BFS完全适用于
tree和graph。因此,把tree的题目练好了,graph的多数题目应该也不会有什么问题才
对。当然graph涉及的算法比tree还是要多的,比如shortest
path,
toposort等等,但是DFS,BFS还是基本中的基本。因此做Leetcode上的tree的题目也相
当于练习了graph的题目了。
由于Tree的题目比较多,我感觉一些可以skip掉,如果时间不充裕的话。或者做一遍即
可,不需要反复练习。这些题目或者太简单,或者面试不太可能碰到。 |
l****i 发帖数: 396 | 2 大牛能指点一下哪些tree的题目要多练 哪些可以skip掉吗? 多谢!! =) |
p*****2 发帖数: 21240 | 3
Balanced Binary Tree
Binary Tree Level Order Traversal II
Maximum Depth of Binary Tree
Minimum Depth of Binary Tree
Same Tree
Symmetric Tree
Unique Binary Search Trees
Unique Binary Search Trees II
Pre-order, In-order, Post-order traversal
需要会recursive和iterative的两种实现方式。可惜Leetcode上只包含了In-order,有
些遗憾。
Tree的serialization/deserialization也是常常被考到的题目,这个Leetcode目前还
没有包含,当然套路还是DFS/BFS。
LinkedList和Binary Tree相互转换的题目。
Convert Sorted List to Binary Search Tree
Flatten Binary Tree to Linked List
(这题原题在CC150是一道双向链表题,不知道Leetcode上怎么改单向了。双向链表应该
更复杂一些,大家要注意一下)
【在 l****i 的大作中提到】 : 大牛能指点一下哪些tree的题目要多练 哪些可以skip掉吗? 多谢!! =)
|
l****i 发帖数: 396 | 4 Mark 多谢!!!!! 期待更多总结贴哇!
【在 p*****2 的大作中提到】 : : Balanced Binary Tree : Binary Tree Level Order Traversal II : Maximum Depth of Binary Tree : Minimum Depth of Binary Tree : Same Tree : Symmetric Tree : Unique Binary Search Trees : Unique Binary Search Trees II : Pre-order, In-order, Post-order traversal
|
x*****0 发帖数: 452 | |