n****t
发帖数: 241 | 1 我看到貌似正确的一个解法，加了很多限制条件。。。
面试题之二叉搜索树的中位数 收藏
这个问题不算是很常见的问题，基本上在中文的论坛社区没有看到过，遇见这个是因为
偶尔在http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi 上面注册了账号而看到的，题目如下：
Given a BST (Binary search Tree) how will you find median in that?
Constraints:
* No extra memory.
* Function should be reentrant (No static, global variables allowed.)
* Median for even no of nodes will be the average of 2 middle elements and
for odd no of terms will be middle element only.
* Algorithm should be efficient in terms of comple... 阅读全帖 |
|
c*****a
发帖数: 808 | 2 简洁版，差别不大
public void preOrderTraverse(BSTNode node){
Stack> stack = new Stack>();
stack.push(node);
while(stack.size()>0){
BSTNode current = stack.pop();
System.out.print(current.data+" ");
if(current.right!=null)
stack.push(current.right);
if(current.left!=null)
stack.push(current.left);
}
}
private void postOrderTraverse(BSTNode node){
Stack> stack = new Stack>(... 阅读全帖 |
|
f*********d
发帖数: 140 | 3 //我上个代码吧, 没有测试过, 有错误或者bug请指出。。。
//这里假设所有节点的值都不一样, 如果存在一样的节点值, 需要一点修改。。。
struct BSTNode {
BSTNode* left;
BSTNode* right;
int val;
}
//print open interval (min_val, max_val) in r
void PrintBST(BSTNode* r, int min_val, int max_val)
{
if(r == NULL) return;
if(r->val <= min_val) PrintBST(r->right, min_val, max_val);
else if(r->val >= max_val) PrintBST(r->left, min_val, max_val);
else {
PrintBST(r->left, min_val, r->val);
cout << r->vale;
PrintBST(r-... 阅读全帖 |
|
a*****2
发帖数: 96 | 4 求最大的s[i]:
//就用二叉树就足够了吧，树的节点里记录比本节点小的个数
public int sln(){
BSTNode root = new BSTNode(a[n-1],0)
int result = 0;
for i in n-2:0{
//O(logn)
result = max(result,insert(root ,a[i],0));
}
return result;
}
class BSTNode{
int value;
int descendants;
BSTNode left = null;
BSTNode right = null;
}
public int insert(BSTNode root, int value, int cnt){
if(root == null)
return 0;
int result = 0;
if(root.value < value){
result += root.descendants+1;
... 阅读全帖 |
|
H***e
发帖数: 476 | 5 这题跟dp啥关系啊？
也用不着dijkstra,就是简单的pre-order traversal就可以勒。
inside a class:
private List minPath = new ArrayList();
private int minSum = Integer.MAX_VALUE;
private void minSumPathFromRootToLeave(BSTNode node,
ArrayList path, int currentSum) {
//path is the path from root to node's parent,
//currentSum is sum from root till node's parent
// add base cases here:
if(node == null){
return;
}
... 阅读全帖 |
|
r******r
发帖数: 700 | 6 写的另一个 iterative 的，就没有问题。这个调试了很久，就是不 work. 每次只是插
入重复插入第一个值。这是把 insert 定义在 BST class 里面。下面另一个
recursive 的，把 insert 定义在 node 里面，也没问题。 贴出我的 node 定义。
谁再看看，上面那个的问题在哪里 （注意，那个 insert 定义在 BST class 里面）？
private static class BSTNode>{
private T value_;
BSTNode left;
BSTNode right;
public BSTNode(T value){
value_ = value;
left = null;
right = null;
}
public void insert(T... 阅读全帖 |
|
h**6
发帖数: 4160 | 7 我把二叉树版本写出来了，大家研究一下：
void duplicate(BSTNode* A)
{
if(A == NULL)
return;
BSTNode* temp = new BSTNode;
temp->left = A->left;
temp->right = A->right;
A->left = temp;
A->right = NULL;
duplicate(temp->left);
duplicate(temp->right);
}
void copy(BSTNode* A)
{
if(A == NULL)
return;
BSTNode* temp = A->left;
if(A->random == NULL)
temp->random = NULL;
else
temp->random = A->random->left;
copy(temp->left);
copy(temp->righ |
|
C******x
发帖数: 91 | 8 卡了一阵子了
知道这里藏龙卧虎, 跪求一个bst中序遍历 c++ class iterator代码参考
也可以私信我, 还请不吝赐教
写了很多次, 但是对于c++迭代器还是不熟悉, c++想写好着实不容易 汗
我写成下面这样, 看起来有点像java的(不对也请指出), c++的该怎么写啊, 跪求指导
和意见
class BSTreeInorderIterator
{
private:
stack st;
public:
BSTreeInorderIterator(BSTNode* root)
{
push_left(root);
}
bool hasNext()
{
return !st.empty();
}
BSTNode* next()
{
BSTNode* node = st.top();
st.pop();
push_left(node->right);
return node;
... 阅读全帖 |
|
r******r
发帖数: 700 | 9 这个版本的 insert 为什么不正确？ 谁能帮忙看看
public void insert1(T value){
if( root == null ){
root = new BSTNode(value);
}else
insertHelper(value, root);
}
private void insertHelper(T value, BSTNode node){
if( value.compareTo(node.value_) < 0 ){
if( node.left == null )
node.left = new BSTNode(node.value_);
else
insertHelper(value, node.left);
}else if( value.compareTo(node.value_) > 0 ){
if( node.right == null )... 阅读全帖 |
|
i****1
发帖数: 445 | 10 public void insert (int value) {
rInsert (value, root);
}
private void rInsert (int value, BSTNode node) {
if (node == null) {
node = new BSTNode (value);
} else if (value < node.value) {
rInsert (value, node.left);
} else if (value > node.value) {
rInsert (value, node.right);
}
}
This approach will work in some programming
languages ... but not Java.
不知为为何上面的程序错了？我看挺好的，为何会出错。
而且答案是java里rinsert()函数需要返回值，如private BSTNode rInsert (int
value
, BSTNode node).
这时为何？ |
|
r******r
发帖数: 700 | 11 这个运行了一下，好像不对。 the path to the deepest node 就是树的 height. 如
果计算 height:
int height(BSTNode node) {
if (node == null)
return 0;
else
return Math.max(height(node.left), height(node.right)) + 1;
}
这就可以吧。height 的定义：
“The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.”
不过原问题好像是要找到 nodes, 那应该是 a list of nodes that have
the same biggest depth (tree'... 阅读全帖 |
|
H***e
发帖数: 476 | 12 第二题，
用往上面反值的方法， 左右子树传值给parent node. 总复杂度为O(n).
inside a class:
BSTNode maxsumNode = null;
int maxValue = Integer.MIN_VALUE;
public void findMaxSumSubtree(BSTNode node, MutableInt sum) {
// base cases:
if (node == null) {
sum.setValue(0);
return;
}
// normal cases:
MutableInt leftSum = new MutableInt();
MutableInt rightSum = new MutableInt();
findMaxSumSubtree(node.left, leftSum);
findMaxSumSubtree... 阅读全帖 |
|
l****p
发帖数: 397 | 13 确实想不出比mlg(N)更快的算法。这题要在30分钟内做完确实很难，我看了楼主的思路
后还用了近50分钟才写完的……
顺便贴上我的实现(Ruby)：
def nearest_nodes root, m, key
node = find_insert root, key
prev = node.prev_node
nex = node.next_node
results = []
m.times do
nearest = nil
if prev and nex
if m-prev.value
nearest = prev
prev = prev.next_node
else
nearest = nex
nex = nex.next_node
end
elsif prev
nearest = prev
prev = prev.prev_node
elsif nex
nearest ... 阅读全帖 |
|
T****U
发帖数: 3344 | 14 这应该是烙印的版本，给两个100的vectors
http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
后面问答区一个烙印贴的
vector v1[100];
vector v2[100];
void VerticalOrder(struct BstNode* root, int index) {
if(!root) return;
if(index < 0) {
v1[-1*index].push_back(root->data);
}
else {
v2[index].push_back(root->data);
}
VerticalOrder(root->left, index - 1);
VerticalOrder(root->right, index + 1);
}
int main()
{
struct BstNode* root = NULL;
root = insert(roo... 阅读全帖 |
|
T****U
发帖数: 3344 | 15 这应该是烙印的版本，给两个100的vectors
http://www.geeksforgeeks.org/print-binary-tree-vertical-order/
后面问答区一个烙印贴的
vector v1[100];
vector v2[100];
void VerticalOrder(struct BstNode* root, int index) {
if(!root) return;
if(index < 0) {
v1[-1*index].push_back(root->data);
}
else {
v2[index].push_back(root->data);
}
VerticalOrder(root->left, index - 1);
VerticalOrder(root->right, index + 1);
}
int main()
{
struct BstNode* root = NULL;
root = insert(roo... 阅读全帖 |
|
r******r
发帖数: 700 | 16 如果计算 deepest node 的整数值，那就是树的高度吧：
“The height of a tree is the length of the path from the root to the
deepest node in the tree. A (rooted) tree with only one node (the root) has
a height of zero.”
这个整值只有一个，就是树的高度。但这个问题的本意好像不是计算树的高度。
但如果要找出具体的 nodes，可能有多个。
看了网上一些相关话题，好像 depth 和 height 的概念有些混淆。比如有计算 最大深
度 的讨论，
public int maxDepth(BSTNode node) {
if (node == null) return 0;
int left = maxDepth(node.left);
int right = maxDepth(node.right);
return 1 + Math.max(left... 阅读全帖 |
|
c*****a
发帖数: 808 | 17 不知道行不行，只测试了几个case
public static int findUni(BSTNode node){
if(node == null) return 0;
if((node.left==null || node.left.data == node.data) &&
(node.right==null ||node.right.data == node.data))
return findUni(node.left) + findUni(node.right) + 1;
else return findUni(node.left) +findUni(node.right);
} |
|
c*****a
发帖数: 808 | 18 那个貌似多余的
我照着你想法写的
static int i=0;
public void findKth(BSTNode node, int k){
if(node == null) return;
findKth(node.right, k );
i++;
if(i==k) System.out.println(node.getData());
findKth(node.left, k );
} |
|
c*****a
发帖数: 808 | 19 练一下 不知道对不对
static int maxPath=0;
private static int longestPath(BSTNode node){
if(node==null) return 0;
int left = longestPath(node.left);
int right = longestPath(node.right);
maxPath = Math.max(left+right, maxPath);
return Math.max(left, right)+1;
} |
|
c*****a
发帖数: 808 | 20 哦，我以为是算edges,这样就5了
static int maxPath=0;
private static int longestPath(BSTNode node){
if(node==null) return 0;
int left = longestPath(node.left);
int right = longestPath(node.right);
maxPath = Math.max(left+right+1, maxPath);
return Math.max(left, right)+1;
} |
|
c*****a
发帖数: 808 | 21 练一下 不知道对不对
static int maxPath=0;
private static int longestPath(BSTNode node){
if(node==null) return 0;
int left = longestPath(node.left);
int right = longestPath(node.right);
maxPath = Math.max(left+right, maxPath);
return Math.max(left, right)+1;
} |
|
c*****a
发帖数: 808 | 22 哦，我以为是算edges,这样就5了
static int maxPath=0;
private static int longestPath(BSTNode node){
if(node==null) return 0;
int left = longestPath(node.left);
int right = longestPath(node.right);
maxPath = Math.max(left+right+1, maxPath);
return Math.max(left, right)+1;
} |
|
