d*******l
发帖数: 338 | 1 我觉得suffix tree可以认为是把一个字符串的所有suffix放进一个trie中，并压缩掉
度为1的节点得到的结果。
所以原则上能用其中一个地方也能用另一个，差别在复杂度上。不过现实中trie还能写
写，suffix tree的O(n)实现不太可能写出来。最多也就能嘴上说说。 |
|
n*******w
发帖数: 687 | 2 可能是吧。数字不记得。但是2比3简单，所以2进制，2-tree了。 |
|
c*****e
发帖数: 3226 | 3 2-3-4 tree, suffix tree, ....
特别是那些business applications适合那种数据类型。。要零时抱佛脚一下。/
wikipedia 有点冗长。 |
|
S****h
发帖数: 558 | 4 It is from Amazon telephone interview. The traditional question:
intersection of two lists. He wanted me to think about alternative of
hashtable. So build a search tree. He then asked what happened if the
list
is so large that it has to be stored across a cluster. How would you
store
this search tree? Any good idea? |
|
S********t
发帖数: 3431 | 5 没印象啊，我对150应该还是很熟悉，难道150出新版了我不知道？
make sure this problem is regarding generic tree, not BST or binary tree |
|
g**u
发帖数: 504 | 6 Imput:
array A, sum s.
Output:
pair (u,v)
Given an sorted array, choose the middle element m, then m is the root of a
balanced BST. If s-m>m, we search the right sub-tree, otherwise we search
the left sub-tree. Doing this recursively, we can find (u,v) in O(log(n)). |
|
c***g
发帖数: 472 | 7 我个人对自己的corner case的考虑一向没有信心，请各位大侠调教一下
int
Tree::getDepth(Node* head) {
if(head == NULL) return 0;
if(head->left == NULL && head->right == NULL) return 0;
int left = getDepth(head->left)+1;
int right = getDepth(head->right)+1;
return (left > right)?left:right;
}
bool
Tree::isBalanced(Node* head) {
if(head == NULL ) return true;
return (isBalanced(head->left)
&& isBalanced(head->right)
&& abs(getDepth(head->left) - getDepth(head... 阅读全帖 |
|
B*******1
发帖数: 2454 | 8 http://www.geeksforgeeks.org/archives/5230
int height(struct node* node)
{
/* base case tree is empty */
if(node == NULL)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + max(height(node->left), height(node->right));
} |
|
d********w
发帖数: 363 | 9 这里面有不少重复计算吧，我面试时也遇到，面试官希望扫描一遍tree就判断出来
int isB(Tree t){
if(!t) return 0;
int left=isB(t.left);
int right=isB(t.right);
if( left >=0 && right >=0 && left - right <= 1 || left -right >=-1)
return (left
else return -1;
} |
|
S******t
发帖数: 151 | 10 。。。这都被误导成啥样了
我相信没有任何Google和Facebook的面试题会用suffix tree的
当然，你如果是说建一个包含所有suffix的trie，那当我没说
trie是需要掌握的
如果谈到suffix tree那肯定是需要用线性构造算法了
那个Ukkonen算法极其复杂，完全不可能是面试难度
甚至acm/icpc题目里面我也基本没见过
如果实在很想了解这方面的一些知识
学一学suffix array我看足够了 |
|
s******o
发帖数: 2233 | 11 第四版的4.8：
You are given a binary tree in which each node contains a value. Design an
algorithm to print all paths which sum up to that value. Note that it can be
any path in the tree - it does not have to start at the root.
书上的解法貌似只考虑root左边或者右边subtree里的path，比如下面这个找sum=6的就
找不出来，
2
1 3
想确认一下我的理解对不对。如果需要考虑这种情况有什么简洁点的做法？ |
|
x*******6
发帖数: 262 | 12 我也有过这个想法。但suffix tree node可以存一个字符串啊。好像suffix tree最好
的implementation是用Ukkonen的方法，这个我还没看 |
|
e********3
发帖数: 229 | 13
node
那样的话suffix tree的构造就不止O（n）了。那这要怎么跟面试官说。
假设不管这个，那我要怎么用一个api来解这题呢？我没见过有suffix tree的api。自
己想一个又怕不严谨 |
|
m*******1
发帖数: 77 | 14 Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
如果中序遍历后存起来自然是好解决，可是不满足空间要求，如何在O(1)空间做到？ |
|
e****e
发帖数: 418 | 15 Binary tree 是暴力解法了吧.
Binary search tree is O(log(n)). |
|
n****r
发帖数: 120 | 16 Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
这道题咋解呢？每个节点DFS？ |
|
C***U
发帖数: 2406 | 17 void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;
if(root == NULL)
return;
current = root;
while(current != NULL)
{
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;
/* Make current as right child of its inorder predeces... 阅读全帖 |
|
R**y
发帖数: 72 | 18 如何Heapify a Binary tree?
我google了一些资料，大部分的思路都是将binary tree 存储到一个数组，然后进行
heapify. 默认这个二叉树是用Node表示。
但是二叉树转换成数组的过程中，需要遍历两次这个树，第一次获得节点数目，第二次
存储节点。这就是2*O(n)了。
板上各位有没有其他的方法，直接在树本身上进行heapify?
谢谢各位 |
|
w****x
发帖数: 2483 | 19 那个是interval tree, 和常说的segment tree不大一样。
好像只能返回一个相交的线段 |
|
f*********m
发帖数: 726 | 20 我觉得没有包含。BST对于节点的顺序有限制，比如BST：1为根，2作为子节点只能在1
右侧。在这种情况下只能有1个bst.
而任意的tree没有这个限制。2可以是1的左或右子节点。所以可以有两个tree.
你的例子中，比如1 * 4 + 4 * 1，第一项是说以1为根，第二项是说以4为根。所以其
实没有包含重复。 |
|
b****g
发帖数: 192 | 21 Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。 |
|
b****g
发帖数: 192 | 22 Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。 |
|
c***s
发帖数: 192 | 23 用两个边界来判断的思路是对的，不过你的codes写得复杂了点。
下面是我写的：
public class ValidateBinarySearchTree {
public boolean isValidBST(TreeNode root, int min, int max) {
if(root == null) return(true);
if(root.val <= min || root.val >= max) return(false);
return(isValidBST(root.left, min, root.val) &&
isValidBST(root.right, root.val, max));
}
public boolean isValidBST(TreeNode root) {
return(isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
}
:
O(
tree |
|
A******g
发帖数: 612 | 24 题目：判断一个binary tree 是否平衡，平衡的定义是任意node，左边subtree和右边
subtree的高度相差不超过1。Careercup150有这道题，用了书上的解法。没有通过全部
测试。觉得careercup解法好像不对。
比如这个
{1,2,3,4,5,#,6,7}
1
/ \
2 3
/\ \
4 5 6
/
7
Careercup是用max depth - min depth = 3-1=2 不平衡
主要是上面的minDepth算法会把1右边substree算成2
请大牛指点！
careercup书上解法：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(... 阅读全帖 |
|
a******3
发帖数: 113 | 25 之前面试被问到。。只想到file system和xml, html是用tree结构的。剩下几个想不到
。。 |
|
b*****u
发帖数: 648 | 26 还有数据库索引是search tree
LRU 使用了双向链表 |
|
l********r
发帖数: 140 | 27 All the solutions I can find will need to use the special character to
represent the empty node. Is there a way to do it without using it?
For example:
a
b c
Will need 4 special character to represent the 4 null children nodes, which
will take too much space. Is there a way to save / load this binary tree
without using the special character?
(note: we are talking about a regular binary tree. It may not be balanced,
it is not a BST.) |
|
l****i
发帖数: 396 | 28 trie 还是 suffix tree？
suffix tree是写最优的那个吗？ |
|
S******t
发帖数: 151 | 29 我对于这个问题的理解是最好用Aho-Corasick Algorithm而不是用Suffix Tree，Aho-
Corasick就是做多串匹配用的，实现复杂度也低很多。
http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matchi
Suffix Tree的线性构造算法是非常复杂的，我的印象里面要在300行以上(以Ukkonen算
法为例)，而非线性的构造算法则毫无意义，还不如直接brute force的去匹配(比如说
CC150上的算法)。
Suffix Array的实现稍微简单一些，但是Linear Time的构造算法仍然并不好理解，我
的印象里三分法的实现复杂度应该在30-50行，而且几乎是千篇一律的模板，倍增法的
实现虽然好写一些但是复杂度就不是O(n)而是O(nlogn)的，不知道最近是不是有更好的
实现方式了，还请各位不吝指教。。。 |
|
j*****n
发帖数: 1545 | 30 Interval tree 返回的是 所有 包括那个点的 interval.
我觉得挺有用的, 很多和 interval 有关的问题都能用到 interval tree. |
|
m****l
发帖数: 61 | 31 面试真心用不到这个。
我面了6家onsite，几次跟interviewer说可以用segment tree，发现对方完全不知道什
么是segment tree。所有题目都可以贪心或者2分。
最失败的是我没记清楚细节，当场也实现不出来。。。 |
|
g*******s
发帖数: 2963 | 32 好像看到最近不少面经都出现了跟interval有关的。
到底什么情况下才需要当场先build一个interval tree然后再往下做？
我看了看leetcode上两道跟interval有关的（insert interval 和 merge interval）
都需要build整个tree么？ |
|
b****g
发帖数: 192 | 33 给定字符串T，然后从后向前扫一遍，能建立T的suffix tree。这一步我会做。
但是从后向前扫描有缺陷，那就是必须知道字符串的结尾，所以不能用于stream相关的
场合及压缩算法。
我知道有方法可以从前向后扫描，建立suffix tree。我从没做过这种算法。面试时有
人问这种算法吗？ |
|
o******e
发帖数: 1001 | 34 刚开始做leetcode,发现测试code的时候，leetcode tree的输入方法有点不懂。比如
{1,#,2}，{1,2,3,4,#,#,5}分别对应什么样点的binary tree? 多谢！ |
|
y*****i
发帖数: 141 | 35 字典是已知的，pattern是未知的，且多个。这样是不是KMP就不如suffix tree了。每
一个新pattern都得重新搜一次。
就是做题的时候suffix tree感觉比KMP难写多了。。。 |
|
g**G
发帖数: 767 | 36 如果没理解错的话，应该是trie而不是suffix tree做
trie一般用于这种类似字典的查找，suffix tree一般用来重复查找同一个字符串的子串 |
|
l*******0
发帖数: 63 | 37 我觉得trie不太行吧？trie是找前缀的，但他这个是要找子串。比如字典里有abcd，
mcd, ncd, 然后要找所有含cd的，那trie岂不是一个都找不出来。可是如果是suffix
tree的话 难道为每一个字典里的string都建一课suffix tree？我觉得可能用那个
rolling hash比较不错。
子串 |
|
u*****o
发帖数: 1224 | 38 且听本姑娘一一道来
1. pre-order recursive solution
2. pre-order iterative solution using stack
3. pre-order iteration using an iterator with stack
4. in-order recursive solution
5. in-order iterative solution using stack
6. in-order iteration using an iterator with stack
7. in-order iterative solution without stack, without parent pointer (
threaded tree)
8. in-order iterative solution without stack, with parent pointer
9. post-order recursive
10. post-order iterative using one stack
11. post-order itera... 阅读全帖 |
|
x******e
发帖数: 18 | 39 在leetcode上判断一个二叉树是不是binary search tree，用in order traversal方法
，结果{-1，0}等test case通不过。上代码：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
int last_val = INT_MIN;
class Solution {
public:
bool isValidBST(TreeNode *root) {
if (root == NULL) {
return true;
}
if (!isValidBST(root->left)) {
return false;
}
... 阅读全帖 |
|
h****p
发帖数: 87 | 40 Find the node with given value in binary tree in in-order way,and return it;
PS: the binary tree may include two nodes with the same value.
感觉老写不对
哪位大牛分享下solution？
谢谢 |
|
l********r
发帖数: 140 | 41 "Given the root of a binary tree (not balanced), heapify it."
It asks to heapify, it does not ask to balance the tree. |
|
l********r
发帖数: 140 | 42 "Given the root of a binary tree (not balanced), heapify it."
It asks to heapify, it does not ask to balance the tree. |
|
a**d
发帖数: 85 | 43 http://www.geeksforgeeks.org/diameter-of-a-binary-tree/
看到这个题。
我觉得可以就用一个class instance variable去记录max就好了：
int max=0;
public int diameter(Tree root) {
if(root==null) return 0;
int l=diameter(root.left);
int r=diameter(root.right);
max=Math.max(max,l+r+1);
return l>r:l+1:r+1;
}
感觉这样没错吧。谢了 |
|
b****z
发帖数: 176 | 44 leetcode的一道题目，树的中序遍历，用普通的方法可以跑过。
但是网上看到有人用Threaded Binary Tree 。感觉这已经比较难了，像这样的问题
Threaded Binary Tree ， 在准备interview的时候需要掌握吗？ 会不会超过难度？ |
|
y***n
发帖数: 1594 | 45 就想问问大家。我的基本知识不好。都是想把Tree搞得balance,很多书都讲 Red Back
Tree，不知道为什么，我觉得挺难的。 |
|
t******i
发帖数: 483 | 46 http://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int minDepth(TreeNode root) {
getMinDepth(root, 0);
return min;
}
public static int min = Integer.MAX_VALUE;
public void getMinDepth(TreeNode node, int level) {
if (node == null) {
if (min > level... 阅读全帖 |
|
m**********j
发帖数: 610 | 47
tree就是graph的一种，无向无环图
所以graph的BFS跟DFS拿到tree上直接跑 |
|
k***g
发帖数: 166 | 48 感觉许多字符串问题都可以用suffix tree解，但面试的时候会实际写怎么构造一棵
suffix tree吗？大家遇到过吗？ |
|
R*****i
发帖数: 2126 | 49 感觉比较tree和hashmap就是比较牛头和马嘴，除了都是collection以外，没有任何相
似之处。tree是一种hierarchy,寻找的cost是O(log(n)),并且可以让您快速找到大小顺
序中的左邻右舍，hashmap是hashtable?, 根据key找value，寻找的cost是O(1). |
|
f*******w
发帖数: 1243 | 50 个人感觉两点：一是复杂度，O(1)和O(logn)的区别; 二是tree结构通常是说BST，所以
整体是排好序的，而hashmap不是。所以当你需要in order输出，或者找到前一个/后一
个element的时候用tree比hash好。
反正我面试的时候碰到这题回答这两点一般就move on了…… |
|
