b*****u
发帖数: 648 | |
t*********n
发帖数: 89 | |
p*****2
发帖数: 21240 | |
b*****u
发帖数: 648 | 4 那样达不到O(1)吧
【在 p*****2 的大作中提到】
: traverse一遍就可以了吧？
|
p*****2
发帖数: 21240 | 5
两个变量就可以了吧？
【在 b*****u 的大作中提到】
: 那样达不到O(1)吧
|
e****e
发帖数: 418 | 6 Assume there is only one value got duplicated.
global variable: int count = 0;
void inorderDFS(Node n, MutableInt prev) {
if ( node == null )
return;
inorderDFS( node.left, prev );
if ( n.val == prev.val )
count++;
pre.val = node.val;
inorderDFS( node.right, prev );
}
invoke: inorderDFS( root, new MutableInt() );
return: count
class MutableInt {
int val;
} |
l*****a
发帖数: 14598 | 7 讨论一下
BST到底是否允许有重复元素
【在 b*****u 的大作中提到】
: 要求 O(n)时间 O(1)空间，怎么搞？
: glassdoor上看到的
: http://www.glassdoor.com/Interview/count-the-number-of-duplicat
|
G****A
发帖数: 4160 | 8 原题目是 "count the number of duplicates in a binary tree in O(n) time O(1)
space"
没看到说BST啊
【在 b*****u 的大作中提到】
: 要求 O(n)时间 O(1)空间，怎么搞？
: glassdoor上看到的
: http://www.glassdoor.com/Interview/count-the-number-of-duplicat
|
e****e
发帖数: 418 | 9 by Interview Candidate: Oct 24, 2012
yes you are correct, I meant a BST
)
【在 G****A 的大作中提到】
: 原题目是 "count the number of duplicates in a binary tree in O(n) time O(1)
: space"
: 没看到说BST啊
|
l*****a
发帖数: 14598 | 10 In computer science, a binary search tree (BST), which may sometimes also be
called an ordered or sorted binary tree, is a node-based binary tree data
structure which has the following properties:[1]
The left subtree of a node contains only nodes with keys less than the node'
s key.
The right subtree of a node contains only nodes with keys greater than the
node's key.
Both the left and right subtrees must also be binary search trees.
There must be no duplicate nodes.
【在 e****e 的大作中提到】
: by Interview Candidate: Oct 24, 2012
: yes you are correct, I meant a BST
:
: )
|
|
|
e****e
发帖数: 418 | 11 在面试中, BST和wiki上的定义弱相关，和面试官头脑里的定义强相关。。。我们现在
也不知道当时的情况，就姑且认为是有一个节点可以重复的树，其他节点满足BST?
be
node'
【在 l*****a 的大作中提到】
: In computer science, a binary search tree (BST), which may sometimes also be
: called an ordered or sorted binary tree, is a node-based binary tree data
: structure which has the following properties:[1]
: The left subtree of a node contains only nodes with keys less than the node'
: s key.
: The right subtree of a node contains only nodes with keys greater than the
: node's key.
: Both the left and right subtrees must also be binary search trees.
: There must be no duplicate nodes.
|
G****A
发帖数: 4160 | 12 Now, I see.
【在 e****e 的大作中提到】
: by Interview Candidate: Oct 24, 2012
: yes you are correct, I meant a BST
:
: )
|
p*****2
发帖数: 21240 | 13
可以有重复
【在 l*****a 的大作中提到】
: 讨论一下
: BST到底是否允许有重复元素
|
l*****a
发帖数: 14598 | 14 哪本书？
【在 p*****2 的大作中提到】
:
: 可以有重复
|
p*****2
发帖数: 21240 | 15
CC150
【在 l*****a 的大作中提到】
: 哪本书？
|
p*****p
发帖数: 379 | 16 假设一样的走左树，两个变量怎么找下面这个？
(4, 2, #, 1, 3, #, 2, #, 4)
【在 p*****2 的大作中提到】
:
: CC150
|
p*****2
发帖数: 21240 | 17
能不能画个树出来看？
【在 p*****p 的大作中提到】
: 假设一样的走左树，两个变量怎么找下面这个？
: (4, 2, #, 1, 3, #, 2, #, 4)
|
p*****p
发帖数: 379 | 18
【在 p*****2 的大作中提到】
:
: 能不能画个树出来看？
|
p*****2
发帖数: 21240 | |
e****e
发帖数: 418 | 20 我觉得是。
【在 p*****2 的大作中提到】
: 1 2 2 3 4 4
: 这个顺序走吧？
|
b*****u
发帖数: 648 | 21 两个变量的方法能不能elaborate一下或者贴个链接?
我目前搜到的不用递归,不用栈的方法都assume有父指针 |
p*****p
发帖数: 379 | 22 了解了，Inorder+两个变量就够了
【在 p*****2 的大作中提到】
: 1 2 2 3 4 4
: 这个顺序走吧？
|
