f********3
发帖数: 210 | 1 如果节点里面没存the number of nodes，有啥好办法么？(一个人的面经里面说，面
试官指出节点里面没存the number of nodes under a root)
或者直接中序遍历？
欢迎讨论&&指点 :) |
c**y
发帖数: 172 | 2 define two helper functions first.
1. min_BST(root)
2. succ_BST(curr)
then traverse the BST in the following way
for (node = min_BST(root); node; node = succ_BST(node)) {
// do something for each node
}
This is how a BST is traversed. |
i******t
发帖数: 158 | 3 按right-root-left 的顺序中序遍历, 第k个数就是 |
v*********u
发帖数: 4 | 4 顶三楼.
有个地方要注意
1.如果允许静态/全局变量,问题很容易,找到传值回来就行
2.如果1不行,需要自定义类,里面包含counter,返回值,数到k以后的直接返回,而且不去
其他分支
面试一般很有可能开始允许你用static,然后等你全对了问你不准的情况 |
m**q
发帖数: 189 | 5 不需要static吧，直接传参数记录当前第几个就行了
PS. 这个题应该也可以用分治来做，期望复杂度应该也是O(N)。
(和在数组中找第k大数是类似的）
【在 v*********u 的大作中提到】
: 顶三楼.
: 有个地方要注意
: 1.如果允许静态/全局变量,问题很容易,找到传值回来就行
: 2.如果1不行,需要自定义类,里面包含counter,返回值,数到k以后的直接返回,而且不去
: 其他分支
: 面试一般很有可能开始允许你用static,然后等你全对了问你不准的情况
|
f********3
发帖数: 210 | 6 succ_BST 有啥好的算法么？
【在 c**y 的大作中提到】
: define two helper functions first.
: 1. min_BST(root)
: 2. succ_BST(curr)
: then traverse the BST in the following way
: for (node = min_BST(root); node; node = succ_BST(node)) {
: // do something for each node
: }
: This is how a BST is traversed.
|
f****4
发帖数: 1359 | 7 节点里面存the number of nodes of current tree/subtree是
clrs 14.1
BST min & BST Succ
clrs 12.2
clrs(Introduction to algorithms 2nd)
【在 f********3 的大作中提到】
: succ_BST 有啥好的算法么？
|
f********3
发帖数: 210 | 8 嗯！多谢啦！
【在 f****4 的大作中提到】
: 节点里面存the number of nodes of current tree/subtree是
: clrs 14.1
: BST min & BST Succ
: clrs 12.2
: clrs(Introduction to algorithms 2nd)
|
x*********s
发帖数: 2604 | 9 void findKthLargestInBST(Node* p, int& counter, int k)
{
if(!p || k < 0)
return;
findKthLargestInBST(p->right,counter,k);
counter++;
if(counter == k)
{
cout<value;
return;
}
findKthLargestInBST(p->left,counter,k);
} |
f********3
发帖数: 210 | 10 Thanks~~~~先顶再看
【在 x*********s 的大作中提到】
: void findKthLargestInBST(Node* p, int& counter, int k)
: {
: if(!p || k < 0)
: return;
: findKthLargestInBST(p->right,counter,k);
: counter++;
: if(counter == k)
: {
: cout<value;
: return;
|
