给定带有整数值的bst作为键如何在bst中找到最接近该键的节点？ BST使用节点对象（Java）表示。最接近的是例如4,5,9，如果钥匙是6，它将返回5 ..
像找到元素一样遍历树。当您这样做时，记录最接近您的键的值。现在，当您没有找到密钥本身的节点时，返回记录的值。
因此，如果您在下面的树中寻找关键的3，您将最终在节点6上找不到匹配但是您的记录值将是2，因为这是您所遍历的所有节点中最接近的键（2，7， 6）。
2
1 7
6 8
这是java中的工作解决方案，它使用BST的特性和附加整数来存储最小差异
public class ClosestValueBinaryTree {
static int closestValue;
public static void closestValueBST(Node22 node, int target) {
if (node == null) {
return;
}
if (node.data - target == 0) {
closestValue = node.data;
return;
}
if (Math.abs(node.data - target) < Math.abs(closestValue - target)) {
closestValue = node.data;
}
if (node.data - target < 0) {
closestValueBST(node.right, target);
} else {
closestValueBST(node.left, target);
}
}
}
运行时复杂度 - O（logN）
时空复杂度 - O（1）
最简单的解决方案是从何时开始递归树
由您决定。
遍历需要O（n）时间。我们可以在上下进行吗？喜欢这个递归代码：
Tnode * closestBST(Tnode * root, int val){
if(root->val == val)
return root;
if(val < root->val){
if(!root->left)
return root;
Tnode * p = closestBST(root->left, val);
return abs(p->val-val) > abs(root->val-val) ? root : p;
}else{
if(!root->right)
return root;
Tnode * p = closestBST(root->right, val);
return abs(p->val-val) > abs(root->val-val) ? root : p;
}
return null;
}
这是Python中的递归解决方案：
def searchForClosestNodeHelper(root, val, closestNode):
if root is None:
return closestNode
if root.val == val:
return root
if closestNode is None or abs(root.val - val) < abs(closestNode.val - val):
closestNode = root
if val < root.val:
return searchForClosestNodeHelper(root.left, val, closestNode)
else:
return searchForClosestNodeHelper(root.right, val, closestNode)
def searchForClosestNode(root, val):
return searchForClosestNodeHelper(root, val, None)
它可以在O（log * n *）时间内解决。
该算法可以使用以下C ++代码实现：
BinaryTreeNode* getClosestNode(BinaryTreeNode* pRoot, int value)
{
BinaryTreeNode* pClosest = NULL;
int minDistance = 0x7FFFFFFF;
BinaryTreeNode* pNode = pRoot;
while(pNode != NULL){
int distance = abs(pNode->m_nValue - value);
if(distance < minDistance){
minDistance = distance;
pClosest = pNode;
}
if(distance == 0)
break;
if(pNode->m_nValue > value)
pNode = pNode->m_pLeft;
else if(pNode->m_nValue < value)
pNode = pNode->m_pRight;
}
return pClosest;
}
您可以访问my blog了解更多详情。
“左右遍历并找到最接近的”方法的问题在于它取决于输入元素以创建BST的顺序。如果我们在11搜索BST序列22,15,16,6,14,3,1,90，则上述方法将返回15，而正确的答案是14.唯一的方法应该是使用递归来遍历所有节点，返回最接近的一个作为递归函数的结果。这将给我们最接近的价值
这可以使用Queue和ArrayList来完成。队列将用于在树上执行广度优先搜索。 ArrayList将用于以广度优先顺序存储树的元素。这是实现相同的代码
Queue queue = new LinkedList();
ArrayList list = new ArrayList();
int i =0;
public Node findNextRightNode(Node root,int key)
{
System.out.print("The breadth first search on Tree : \t");
if(root == null)
return null;
queue.clear();
queue.add(root);
while(!queue.isEmpty() )
{
Node node = (Node)queue.remove();
System.out.print(node.data + " ");
list.add(node);
if(node.left != null) queue.add(node.left);
if(node.right !=null) queue.add(node.right);
}
Iterator iter = list.iterator();
while(iter.hasNext())
{
if(((Node)iter.next()).data == key)
{
return ((Node)iter.next());
}
}
return null;
}
void closestNode(Node root, int k , Node result) {
if(root == null)
{
return; //currently result is null , so it will be the result
}
if(result == null || Math.abs(root.data - k) < Math.abs(result.data - k) )
{
result == root;
}
if(k < root.data)
{
closestNode(root.left, k, result)
}
else
{
closestNode(root.right, k, result);
}
}
下面有一个与我有不同的样本。
public Node findNearest(Node root, int k) {
if (root == null) {
return null;
}
int minDiff = 0;
Node minAt = root;
minDiff = Math.abs(k - root.data);
while (root != null) {
if (k == root.data) {
return root;
}
if (k < root.data) {
minAt = updateMin(root, k, minDiff, minAt);
root = root.left;
} else if (k > root.data) {
minAt = updateMin(root, k, minDiff, minAt);
root = root.right;
}
}
return minAt;
}
private Node updateMin(Node root, int k, int minDiff, Node minAt) {
int curDif;
curDif = Math.abs(k - root.data);
if (curDif < minDiff) {
minAt = root;
}
return minAt;
}
以下是查找BST中最接近元素的完整Java代码。
package binarytree;
class BSTNode {
BSTNode left,right;
int data;
public BSTNode(int data) {
this.data = data;
this.left = this.right = null;
}
}
class BST {
BSTNode root;
public static BST createBST() {
BST bst = new BST();
bst.root = new BSTNode(9);
bst.root.left = new BSTNode(4);
bst.root.right = new BSTNode(17);
bst.root.left.left = new BSTNode(3);
bst.root.left.right= new BSTNode(6);
bst.root.left.right.left= new BSTNode(5);
bst.root.left.right.right= new BSTNode(7);
bst.root.right.right = new BSTNode(22);
bst.root.right.right.left = new BSTNode(20);
return bst;
}
}
public class ClosestElementInBST {
public static void main(String[] args) {
BST bst = BST.createBST();
int target = 18;
BSTNode currentClosest = null;
BSTNode closestNode = findClosestElement(bst.root, target, currentClosest);
if(closestNode != null) {
System.out.println("Found closest node: " + closestNode.data);
}
else {
System.out.println("Couldn't find closest node.");
}
}
private static BSTNode findClosestElement(BSTNode node, int target, BSTNode currentClosest) {
if(node == null) return currentClosest;
if(currentClosest == null ||
(currentClosest != null && (Math.abs(currentClosest.data - target) > Math.abs(node.data - target)))) {
currentClosest = node;
}
if(node.data == target) return node;
else if(target < node.data) {
return findClosestElement(node.left, target, currentClosest);
}
else { //target > node.data
currentClosest = node;
return findClosestElement(node.right, target, currentClosest);
}
}
}