给予 二叉搜索树 和一个数字N，任务是在二元搜索树中找到大于或等于N的最小数字。如果元素存在，则打印该元素的值，否则打印-1。
null
例如：
输入：N=20 产出：21 说明：21是大于20的最小元素。
输入：N=18 产出：19 说明：19是大于18的最小元素。
方法： 其思想是遵循递归方法来解决问题，即从根开始搜索元素。
- 如果有一个叶节点的值小于N，则元素不存在并返回-1。
- 否则，如果节点的值大于或等于N，且左子节点为NULL或小于N，则返回节点值。
- 否则，如果节点的值小于N，则在右侧子树中搜索元素。
- 否则，根据left或right值递归调用函数，在左子树中搜索元素。
C++
// C++ program to find the smallest value // greater than or equal to N #include <bits/stdc++.h> using namespace std; struct Node { int data; Node *left, *right; }; // To create new BST Node Node* createNode( int item) { Node* temp = new Node; temp->data = item; temp->left = temp->right = NULL; return temp; } // To add a new node in BST Node* add(Node* node, int key) { // if tree is empty return new node if (node == NULL) return createNode(key); // if key is less then or greater then // node value then recur down the tree if (key < node->data) node->left = add(node->left, key); else if (key > node->data) node->right = add(node->right, key); // return the (unchanged) node pointer return node; } // function to find min value less then N int findMinforN(Node* root, int N) { // If leaf node reached and is smaller than N if (root->left == NULL && root->right == NULL && root->data < N) return -1; // If node's value is greater than N and left value // is NULL or smaller then return the node value if ((root->data >= N && root->left == NULL) || (root->data >= N && root->left->data < N)) return root->data; // if node value is smaller than N search in the // right subtree if (root->data <= N) return findMinforN(root->right, N); // if node value is greater than N search in the // left subtree else return findMinforN(root->left, N); } // Drivers code int main() { /* 19 / 7 21 / 3 11 / 9 14 */ Node* root = NULL; root = add(root, 19); root = add(root, 7); root = add(root, 3); root = add(root, 11); root = add(root, 9); root = add(root, 13); root = add(root, 21); int N = 18; cout << findMinforN(root, N) << endl; return 0; } |
JAVA
// Java program to find the smallest value // greater than or equal to N import java.util.*; class GFG { static class Node { int data; Node left, right; }; // To create new BST Node static Node createNode( int item) { Node temp = new Node(); temp.data = item; temp.left = temp.right = null ; return temp; } // To add a new node in BST static Node add(Node node, int key) { // if tree is empty return new node if (node == null ) return createNode(key); // if key is less then or greater then // node value then recur down the tree if (key < node.data) node.left = add(node.left, key); else if (key > node.data) node.right = add(node.right, key); // return the (unchanged) node pointer return node; } // function to find min value less then N static int findMinforN(Node root, int N) { // If leaf node reached and is smaller than N if (root.left == null && root.right == null && root.data < N) return - 1 ; // If node's value is greater than N and left value // is null or smaller then return the node value if ((root.data >= N && root.left == null ) || (root.data >= N && root.left.data < N)) return root.data; // if node value is smaller than N search in the // right subtree if (root.data <= N) return findMinforN(root.right, N); // if node value is greater than N search in the // left subtree else return findMinforN(root.left, N); } // Driver Code public static void main(String[] args) { /* 19 / 7 21 / 3 11 / 9 14 */ Node root = null ; root = add(root, 19 ); root = add(root, 7 ); root = add(root, 3 ); root = add(root, 11 ); root = add(root, 9 ); root = add(root, 13 ); root = add(root, 21 ); int N = 18 ; System.out.println(findMinforN(root, N)); } } // This code is contributed by Rajput-Ji |
Python3
# Python program to find the smallest value # greater than or equal to N class Node: def __init__( self ): self .data = 0 self .left = None self .right = None # To create new BST Node def createNode(item: int ): temp = Node() temp.data = item temp.left = temp.right = None return temp # To add a new node in BST def add(node: Node, key: int ): # if tree is empty return new node if node is None : return createNode(key) # if key is less then or greater then # node value then recur down the tree if key < node.data: node.left = add(node.left, key) elif key > node.data: node.right = add(node.right, key) # return the (unchanged) node pointer return node # function to find min value less then N def findMinforN(root: Node, N: int ): # If leaf node reached and is smaller than N if root.left is None and root.right is None and root.data < N: return - 1 # If node's value is greater than N and left value # is NULL or smaller then return the node value if root.data > = N and root.left is None or root.data > = N and root.left.data < N: return root.data # if node value is smaller than N search in the # right subtree if root.data < = N: return findMinforN(root.right, N) # if node value is greater than N search in the # left subtree else : return findMinforN(root.left, N) # Driver Code if __name__ = = "__main__" : ''' 19 / 7 21 / 3 11 / 9 14 ''' root = Node() root = add(root, 19 ) root = add(root, 7 ) root = add(root, 3 ) root = add(root, 11 ) root = add(root, 9 ) root = add(root, 13 ) root = add(root, 21 ) N = 18 print (findMinforN(root, N)) # This code is contributed by # sanjeev2552 |
C#
// C# program to find the smallest value // greater than or equal to N using System; class GFG { class Node { public int data; public Node left, right; }; // To create new BST Node static Node createNode( int item) { Node temp = new Node(); temp.data = item; temp.left = temp.right = null ; return temp; } // To add a new node in BST static Node add(Node node, int key) { // if tree is empty return new node if (node == null ) return createNode(key); // if key is less then or greater then // node value then recur down the tree if (key < node.data) node.left = add(node.left, key); else if (key > node.data) node.right = add(node.right, key); // return the (unchanged) node pointer return node; } // function to find min value less then N static int findMinforN(Node root, int N) { // If leaf node reached and is smaller than N if (root.left == null && root.right == null && root.data < N) return -1; // If node's value is greater than N and left value // is null or smaller then return the node value if ((root.data >= N && root.left == null ) || (root.data >= N && root.left.data < N)) return root.data; // if node value is smaller than N search in the // right subtree if (root.data <= N) return findMinforN(root.right, N); // if node value is greater than N search in the // left subtree else return findMinforN(root.left, N); } // Driver Code public static void Main(String[] args) { /* 19 / 7 21 / 3 11 / 9 14 */ Node root = null ; root = add(root, 19); root = add(root, 7); root = add(root, 3); root = add(root, 11); root = add(root, 9); root = add(root, 13); root = add(root, 21); int N = 18; Console.WriteLine(findMinforN(root, N)); } } // This code is contributed by Princi Singh |
Javascript
<script> // javascript program to find the smallest value // greater than or equal to N class Node { constructor() { this .data = 0; this .left = null ; this .right = null ; } }; // To create new BST Node function createNode(item) { var temp = new Node(); temp.data = item; temp.left = temp.right = null ; return temp; } // To add a new node in BST function add(node, key) { // if tree is empty return new node if (node == null ) return createNode(key); // if key is less then or greater then // node value then recur down the tree if (key < node.data) node.left = add(node.left, key); else if (key > node.data) node.right = add(node.right, key); // return the (unchanged) node pointer return node; } // function to find min value less then N function findMinforN(root, N) { // If leaf node reached and is smaller than N if (root.left == null && root.right == null && root.data < N) return -1; // If node's value is greater than N and left value // is null or smaller then return the node value if ((root.data >= N && root.left == null ) || (root.data >= N && root.left.data < N)) return root.data; // if node value is smaller than N search in the // right subtree if (root.data <= N) return findMinforN(root.right, N); // if node value is greater than N search in the // left subtree else return findMinforN(root.left, N); } // Driver Code /* 19 / 7 21 / 3 11 / 9 14 */ var root = null ; root = add(root, 19); root = add(root, 7); root = add(root, 3); root = add(root, 11); root = add(root, 9); root = add(root, 13); root = add(root, 21); var N = 18; document.write(findMinforN(root, N)); // This code is contributed by famously. </script> |
输出：
19
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
