给定一个二叉搜索树和目标节点K。任务是找到与给定目标值K绝对差值最小的节点。 注： 使用的方法应该有恒定的额外空间消耗O（1）。不应使用递归或类似堆栈/队列的容器。
null
![图片[1]-在二叉搜索树中寻找最近的元素|节省空间的方法-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_BinarySearchTree.png)
例如：
Input: k = 4Output: 4Input: k = 18Output: 17
中提到的一个简单解决方案 这 post使用递归来获取二叉搜索树中最接近键的元素。上述post中使用的方法由于递归而消耗了O（n）额外的空间。 现在，我们可以使用 莫里斯穿越 这是一种节省空间的方法，可以在恒定空间O（1）中进行有序树遍历，而不使用递归或堆栈/队列。 Morris traversal基于 线程二叉树 它利用树中的空指针，使它们指向某些后续或前置节点。与具有n个节点的二叉树一样，n+1个空指针会浪费内存。 在下面提到的算法中，我们只需进行有序树遍历，在使用Morris遍历进行有序树遍历时，我们检查节点数据和密钥之间的差异，并维护两个变量“diff”和“closest”，当我们发现离密钥更近的节点时，这两个变量会更新。当我们完成完整的顺序树遍历时，我们有了最近的节点。 算法 :
1) Initialize Current as root.2) Initialize a variable diff as INT_MAX.3)initialize a variable closest(pointer to node) which will be returned.4) While current is not NULL: 4.1) If the current has no left child: a) If the absolute difference between current's data and the key is smaller than diff: 1) Set diff as the absolute difference between the current node and the key. 2) Set closest as the current node. b)Otherwise, Move to the right child of current. 4.2) Else, here we have 2 cases: a) Find the inorder predecessor of the current node. Inorder predecessor is the rightmost node in the left subtree or left child itself. b) If the right child of the inorder predecessor is NULL: 1) Set current as the right child of its inorder predecessor(Making threads between nodes). 2) Move current node to its left child. c) Else, if the threaded link between the current node and it's inorder predecessor already exists : 1) Set right pointer of the inorder predecessor node as NULL. 2) If the absolute difference between current's data and the key is smaller than diff: a) Set diff variable as the absolute difference between the current node and the key. b) Set closest as the current node. 3) Move current to its right child.5)By the time we have traversed the whole tree, we have the closest node, so we simply return closest.
以下是上述方法的实施情况：
C++
// CPP program to find closest value in // a Binary Search Tree. #include <iostream> #include <limits.h> using namespace std; // Tree Node struct Node { int data; Node *left, *right; }; // Utility function to create a new Node Node* newNode( int data) { Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp; } // Function to find the Node closest to the // given key in BST using Morris Traversal Node* closestNodeUsingMorrisTraversal(Node* root, int key) { int diff = INT_MAX; Node* curr = root; Node* closest; while (curr) { if (curr->left == NULL) { // updating diff if the current diff is // smaller than prev difference if (diff > abs (curr->data - key)) { diff = abs (curr->data - key); closest = curr; } curr = curr->right; } else { // finding the inorder predecessor Node* pre = curr->left; while (pre->right != NULL && pre->right != curr) pre = pre->right; if (pre->right == NULL) { pre->right = curr; curr = curr->left; } // threaded link between curr and // its predecessor already exists else { pre->right = NULL; // if a closer Node found, then update // the diff and set closest to current if (diff > abs (curr->data - key)) { diff = abs (curr->data - key); closest = curr; } // moving to the right child curr = curr->right; } } } return closest; } // Driver Code int main() { /* Constructed binary tree is 5 / 3 9 / / 1 2 8 12 */ Node* root = newNode(5); root->left = newNode(3); root->right = newNode(9); root->left->left = newNode(1); root->left->right = newNode(2); root->right->left = newNode(8); root->right->right = newNode(12); cout << closestNodeUsingMorrisTraversal(root, 10)->data; return 0; } |
JAVA
// Java program to find closest value in // a Binary Search Tree. class GFG { // Tree Node static class Node { int data; Node left, right; }; // Utility function to create a new Node static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null ; return temp; } // Function to find the Node closest to the // given key in BST using Morris Traversal static Node closestNodeUsingMorrisTraversal(Node root, int key) { int diff = Integer.MAX_VALUE; Node curr = root; Node closest = null ; while (curr != null ) { if (curr.left == null ) { // updating diff if the current diff is // smaller than prev difference if (diff > Math.abs(curr.data - key)) { diff = Math.abs(curr.data - key); closest = curr; } curr = curr.right; } else { // finding the inorder predecessor Node pre = curr.left; while (pre.right != null && pre.right != curr) pre = pre.right; if (pre.right == null ) { pre.right = curr; curr = curr.left; } // threaded link between curr and // its predecessor already exists else { pre.right = null ; // if a closer Node found, then update // the diff and set closest to current if (diff > Math.abs(curr.data - key)) { diff = Math.abs(curr.data - key); closest = curr; } // moving to the right child curr = curr.right; } } } return closest; } // Driver Code public static void main(String[] args) { /* Constructed binary tree is 5 / 3 9 / / 1 2 8 12 */ Node root = newNode( 5 ); root.left = newNode( 3 ); root.right = newNode( 9 ); root.left.left = newNode( 1 ); root.left.right = newNode( 2 ); root.right.left = newNode( 8 ); root.right.right = newNode( 12 ); System.out.println(closestNodeUsingMorrisTraversal(root, 10 ).data); } } // This code is contributed by Rajput-Ji |
Python3
# Python program to find closest value in # Binary search Tree _MIN = - 2147483648 _MAX = 2147483648 # Helper function that allocates a new # node with the given data and None left # and right poers. class newNode: # Constructor to create a new node def __init__( self , data): self .data = data self .left = None self .right = None # Function to find the Node closest to the # given key in BST using Morris Traversal def closestNodeUsingMorrisTraversal(root,key): diff = _MAX curr = root closest = 0 while (curr) : if (curr.left = = None ) : # updating diff if the current diff is # smaller than prev difference if (diff > abs (curr.data - key)) : diff = abs (curr.data - key) closest = curr curr = curr.right else : # finding the inorder predecessor pre = curr.left while (pre.right ! = None and pre.right ! = curr): pre = pre.right if (pre.right = = None ): pre.right = curr curr = curr.left # threaded link between curr and # its predecessor already exists else : pre.right = None # if a closer Node found, then update # the diff and set closest to current if (diff > abs (curr.data - key)) : diff = abs (curr.data - key) closest = curr # moving to the right child curr = curr.right return closest # Driver Code if __name__ = = '__main__' : """ /* Constructed binary tree is 5 / 3 9 / / 1 2 8 12 */ """ root = newNode( 5 ) root.left = newNode( 3 ) root.right = newNode( 9 ) root.left.right = newNode( 2 ) root.left.left = newNode( 1 ) root.right.right = newNode( 12 ) root.right.left = newNode( 8 ) print (closestNodeUsingMorrisTraversal(root, 10 ).data) # This code is contributed # Shubham Singh(SHUBHAMSINGH10) |
C#
// C# program to find closest value in // a Binary Search Tree. using System; class GFG { // Tree Node public class Node { public int data; public Node left, right; }; // Utility function to create a new Node static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null ; return temp; } // Function to find the Node closest to the // given key in BST using Morris Traversal static Node closestNodeUsingMorrisTraversal(Node root, int key) { int diff = int .MaxValue; Node curr = root; Node closest = null ; while (curr != null ) { if (curr.left == null ) { // updating diff if the current diff is // smaller than prev difference if (diff > Math.Abs(curr.data - key)) { diff = Math.Abs(curr.data - key); closest = curr; } curr = curr.right; } else { // finding the inorder predecessor Node pre = curr.left; while (pre.right != null && pre.right != curr) pre = pre.right; if (pre.right == null ) { pre.right = curr; curr = curr.left; } // threaded link between curr and // its predecessor already exists else { pre.right = null ; // if a closer Node found, then update // the diff and set closest to current if (diff > Math.Abs(curr.data - key)) { diff = Math.Abs(curr.data - key); closest = curr; } // moving to the right child curr = curr.right; } } } return closest; } // Driver Code public static void Main(String[] args) { /* Constructed binary tree is 5 / 3 9 / / 1 2 8 12 */ Node root = newNode(5); root.left = newNode(3); root.right = newNode(9); root.left.left = newNode(1); root.left.right = newNode(2); root.right.left = newNode(8); root.right.right = newNode(12); Console.WriteLine(closestNodeUsingMorrisTraversal(root, 10).data); } } /* This code is contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript program to find closest value in // a Binary Search Tree. // Tree Node class Node { constructor() { this .data = 0; this .left = null ; this .right = null ; } }; // Utility function to create a new Node function newNode(data) { var temp = new Node(); temp.data = data; temp.left = temp.right = null ; return temp; } // Function to find the Node closest to the // given key in BST using Morris Traversal function closestNodeUsingMorrisTraversal(root, key) { var diff = 1000000000; var curr = root; var closest = null ; while (curr != null ) { if (curr.left == null ) { // updating diff if the current diff is // smaller than prev difference if (diff > Math.abs(curr.data - key)) { diff = Math.abs(curr.data - key); closest = curr; } curr = curr.right; } else { // finding the inorder predecessor var pre = curr.left; while (pre.right != null && pre.right != curr) pre = pre.right; if (pre.right == null ) { pre.right = curr; curr = curr.left; } // threaded link between curr and // its predecessor already exists else { pre.right = null ; // if a closer Node found, then update // the diff and set closest to current if (diff > Math.abs(curr.data - key)) { diff = Math.abs(curr.data - key); closest = curr; } // moving to the right child curr = curr.right; } } } return closest; } // Driver Code /* Constructed binary tree is 5 / 3 9 / / 1 2 8 12 */ var root = newNode(5); root.left = newNode(3); root.right = newNode(9); root.left.left = newNode(1); root.left.right = newNode(2); root.right.left = newNode(8); root.right.right = newNode(12); document.write(closestNodeUsingMorrisTraversal(root, 10).data); // This code is contributed by itsok. </script> |
输出：
9
时间复杂性 ：O（n） 辅助空间 ：O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
