这是我在采访中提出的一个问题。对于给定的 BST，找到第 k 个最接近的元素。遍历整棵树是不可接受的。解决方案不应该是 o(n) 并且空间复杂度不是问题。谢谢。
我的尝试 - 遍历树的一个分支以获取可能的元素，然后从这些元素开始遍历分支。
问问题
2607 次
3 回答
1
我想问题是关于找到 BST 中最接近值 V 的第 K 个元素，
注意：不可能在少于 O(n) 的时间内做到这一点，除非 BST 是平衡的，
要找到第 K 个最接近的元素：我们维护 K 个整数，它们是迄今为止与 V 最接近的值，1.访问每个节点（从根开始），我们将节点的值、其前任和后继的值添加到迄今为止看到的最接近的值。（如果数组已满，我们只在靠近 V 的数组中放入一个值。我们用这个值替换最大的那个）
2.如果当前节点的后继节点更接近V，我们选择右分支，如果前任节点更接近，我们选择左分支。
3.我们重复直到没有更多节点可以访问（我们到达叶子）
4.时间复杂度：O(n^2 * k)，如果我们假设k是常数（例如k = 3）并且树是平衡的，那么时间复杂度将是：O(log(n) ^ 2)
Integer[] closest = new Integer[3]; // initialized with null
void find_3rd_closest(Node current , int K){
Node succ = Successor(current);
Node pred = Predecessor(current);
insert(closest , current.val , K);
if (succ != null)
insert(closest , succ.val , K);
if (pred != null)
insert(closest , pred.val , K);
if (succ != null && pred != null)
if (Math.abs(pred.val - K) < Math.abs(succ.val - K))
find_3rd_closest(pred , K);
else
find_3rd_closest(succ , K);
else if (pred != null)
find_3rd_closest(pred , K);
else if (succ != null)
find_3rd_closest(succ , K);
else
return;
}
void insert(int[] closest , int val, int K){
for (int i = 0 ; i < closest.length ; i++){
if (closest[i] != null && Math.abs(K - val) < Math.abs(K - closest[i])){
for (int j = i ; i < closest.length - 1 ; i++){
int temp = closest[i+1];
closest[i+1] = closest[i];
closest[i] = temp;
}
}
closest[i] = succ.value;
}
}
Node Successor(Node current){
if (current.rightChild == null)
return null;
current = current.rightChild;
while (current.leftChild != null)
current = current.leftChild;
return current;
}
Node Predecessor(Node current){
if (current.leftChild == null)
return null;
current = current.leftChild;
while (current.rigthChild != null)
current = current.rightChild;
return current;
}
于 2013-06-08T20:26:52.980 回答
1
首先我们必须找到什么。1，首先你必须得到节点（从 BST 根） 2. 你必须得到它下面和距离 k 的节点。3.你必须得到一个祖先，它是它上面的k个节点。4.你必须得到离它第k远的节点。（同级别或其他级别）
A(8)
/ \
B(6) C(22)
/ \ / \
D(5) E(7) F(17) G(26)
/ \ \
(15)H I(19) N(29)
/ \
(14) K L(20)
Okie 认为这棵树是一棵 BST 树（A、B、C d 不是 BST 的序列，* 将它们视为节点引用来标识节点而不是值 *）我附上了一个代表值的数字。
还有一个考虑。因为它被宣布为 BST 树。不存在父指针。*
你得到了树的根 A 。给定一个数字 17 ，并给定一个 k=2 的值。首先对于数字 17 获取参考 (F) 对于 k=2 ，即从 2 个节点距离从 F 获取树的所有节点。作为 F 的后代，您必须将 K(14) 和 L(20) 检测为的上升F 你必须得到节点 A。你必须再次得到节点 G（2 个节点距离）（尽管没有父指针你必须得到它）。
第一步，首先为数字 -> 17 获取参考 F（您拥有的根）进行简单的二进制搜索。
ArrayList get_it( Node root_node, int number) {
node = root_node;
if (node ==null)
throw new IllegarArgumentException("null root node");
ArrayList pathtracker = new ArrayList();
//is the root node matches
pathtracker.add(node); // fix
if( node.data=number) // fix
return pathtracker;
while(node !=null) {
if ( node.data==number){
return pathtracker;
}
if ( node.data >= number ){
node=node.left;
}
else{
node=node.right;
}
pathtracker.add(node);
} // end of while loop
return new ArrayList(); //search failed node is not present.
// returning empty arrayList
}
现在我们将使用路径跟踪器。这具有从根到该节点的跟踪节点。第 0 个节点是根节点，length()-1 个节点是我们搜索过的节点。
for ( int i = pathtracker.length() - 1 , depth=k ;
( depth => 0 && i => 0 ) ; i--,depth-- ){
if ( i == pathtracker.length() - 1) {//first case
printnodeDistancek( pathtracker.get(i), depth);
}else {
if( pathtracker.get(i).left ! = pathtracker.get(i+1) ){
printnodeDistancek( pathtracker.get(i).left, depth);
}else{
printnodeDistancek( pathtracker.get(i).right, depth);
}
} // end of else block
} // end of loop
void printnodeDistancek( node n, k) {
if (node==null)
return;
if ( k = 0) {
print node.data;
return;
}
printnodeDistancek( n.left, k-1);
printodeDistanceK( node.right, k-1);
}
给定的数字是 17（F 节点），现在如果 k=3，这应该打印 N 和 B。如果 K=4，这应该打印 D(5) 和 E97)
于 2013-05-19T10:17:42.750 回答
0
我将假设两个节点之间的接近度由它们之间的边数定义，并且为了解决歧义，我还假设在距离相等的情况下，父节点最接近，然后是右节点，然后是左节点。
根节点的第 k 个最接近的元素将是第 k 个元素是树的级别顺序遍历。
对于树中的任何节点，我们将从距离 1 边的节点开始，即它的父节点，右，左，然后距离 2 边，即距离 1 的节点的父节点，右，左，依此类推。我们将继续计数，直到我们达到 k 个节点，还要确保我们不计算一个节点两次。考虑以下伪代码。
KthClosest(Node * node, k)
{
std::queue<Node *> queue;
std::map<Node *, bool> mapToCheckIFNodeIsCounted;
int count = 0;
queue.push_back(node);
while(count <k)
{
Node* node = queue.pop();
if(node ->parent != NULL)
{
if(mapToCheckIFNodeIsCounted.find(node->parent) ==mapToCheckIFNodeIsCounted.end())
{
queue->push_back(node->parent);
mapToCheckIFNodeIsCounted.insert(std::pair<node->parent,true>);
}
}
if(node -> right != NULL)
{
if(mapToCheckIFNodeIsCounted.find(node->right) == mapToCheckIFNodeIsCounted.end())
{
queue->push_back(node->right);
mapToCheckIFNodeIsCounted.insert(std::pair<node->right,true>);
}
}
if(node -> left != NULL)
{
if(mapToCheckIFNodeIsCounted.find(node->parent) == mapToCheckIFNodeIsCounted.end())
{
queue->push_back(node->left);
mapToCheckIFNodeIsCounted.insert(std::pair<node->left,true>);
}
}
count++;
}
// Kth node is the node in queue after loop has finished fraversing k closest elements
Node *node = queue.pop();
print(node->value);
}
于 2013-04-02T19:50:51.157 回答