在BST中找到小于K的最大元素
给定一个二叉搜索树和一个整数K，我想找到小于K的最大元素。
在下面的树中
for K = 13, result = 12
for K = 10, result = 8
for K = 1 (or) 2, result = -1
10
5 12
2 8 11 14
int findNum(node* node, int K)
{
if(node == NULL)
{
return -1;
}
else if(K <= node->data)
{
return findNum(node->left,K);
}
else if(K > node->data)
{
int t = findNum(node->right,K);
return t > node->data ? t : node->data;
}
return -1;
}
没有找到相关结果
已邀请:
5 个回复
苛肠倒俱
// Return the greatest int < K in tree, or K if none. int findNum (Node* tree, int K) { int val = K; while( tree ) if( tree->data >= K ) tree = tree->left; else{ val = tree->data; tree = tree->right; } return val; }需复
int findNum (Node *node, int K) { Node* last_right_move = NULL; while (node) { if (K<=node->data) node = node->left; else { last_right_move = node; node = node->right; } } if (last_right_move) return last_right_move->data; else return NOT_FOUND; // defined previously. (-1 may conflict with negative number) }校勒魏寡
。 :-)int largest_num_smaller_than(std::set<int> const& set, int num) { std::set<int>::const_iterator lb(set.lower_bound(num)); return lb == set.begin() ? -1 : *--lb; }土投
温拎凯玛
int findNum (node root, int K) { if(root == null) return -1; if(K > root.val) { if(root.right != null) return findNum(root.right, K); else return root.val; } return findNum(root.left, K); //look in left subtree }