a*******y
发帖数: 1040 | 1 kth min简单，kth max 要是用inverted inorder的话，要是那个值在left tree里，这
样return回来的不对啊 | f*****e
发帖数: 2992 | 2 kth max = n - kth min?
【在 a*******y 的大作中提到】
: kth min简单，kth max 要是用inverted inorder的话，要是那个值在left tree里，这
: 样return回来的不对啊
| d**e
发帖数: 6098 | 3 还没仔细想，但如果kth min简单的话，那要是那个值在right tree是怎么处理？我觉
得min max应该是差不多解法吧
【在 a*******y 的大作中提到】
: kth min简单，kth max 要是用inverted inorder的话，要是那个值在left tree里，这
: 样return回来的不对啊
| a******o
发帖数: 106 | 4 高手麻烦检查下代码C#
就像BST inorder 遍历一样， private method 传递 ref k 和 输出的node， 每次遍
历一个数 k-1, 如果k==0 输出当前node 就行。
Kth Min 和 Max 原理完全一样， 只不过把Inorder 的顺序变成 右节点先考虑而已
。
请大侠们批评指正， 谢谢
private static void findKthMinNodeInBST(BinaryTree.Node n, ref int k
, ref BinaryTree.Node outnode)
{
if (n == null) return;
findKthMinNodeInBST(n.Left, ref k, ref outnode);
k--;
if (k < 0) return;
if (k == 0)
{
outnode = n;
return;
}
findKthMinNodeInBST(n.Right, ref k, ref outnode);
}
public static BinaryTree.Node findKthMinNodeInBST(BinaryTree.Node n,
int k)
{
BinaryTree.Node retnode = null;
findKthMinNodeInBST(n, ref k, ref retnode);
return retnode;
}
public static BinaryTree.Node findKthMaxNodeInBST(BinaryTree.Node n,
int k)
{
BinaryTree.Node retnode = null;
findKthMaxNodeInBST(n, ref k, ref retnode);
return retnode;
}
private static void findKthMaxNodeInBST(BinaryTree.Node n, ref int k
, ref BinaryTree.Node outnode)
{
if (n == null) return;
findKthMaxNodeInBST(n.Right, ref k, ref outnode);
k--;
if (k < 0) return;
if (k == 0)
{
outnode = n;
return;
}
findKthMaxNodeInBST(n.Left, ref k, ref outnode);
} | d****o
发帖数: 1055 | 5 就像找linked list 离尾第k个串一样。设置2个int a b,当a走到第kth min value,然
后a,b同时走。
【在 a*******y 的大作中提到】
: kth min简单，kth max 要是用inverted inorder的话，要是那个值在left tree里，这
: 样return回来的不对啊
| s***y
发帖数: 3042 | 6 为啥不同啊？我是新手，随便写个。
int printKth(Node *root, int *k) {
if( !root )
return 0;
int ret;
ret = printKth(root->right, k);
if(ret == -1)
return -1;
(*k)--;
if((*k)==0) {
cout << "the kth is " << root->data << endl;
return -1;
}
return printKth(root->left, k);
}
【在 a*******y 的大作中提到】
: kth min简单，kth max 要是用inverted inorder的话，要是那个值在left tree里，这
: 样return回来的不对啊
| a*******y
发帖数: 1040 | 7 弄错了
这个应该可以
void findK(Node* p, int& k, int& value) {
if(!p || k < 0) return;
findK(p->right, k, value);
--k;
if(k == 0) {
value = p->value;
cout << p->value;
return;
}
findK(p->left, k, value);
} |
|
