a의 루트를 고려하면 이진 검색 트리 그리고 정수 케이 . 임무는 다음을 찾는 것입니다. 가장 큰 수 이진 검색 트리에서 미만 또는 동일한 그러한 요소가 존재하지 않으면 k에 -1을 인쇄합니다.
예:
입력:
삽입 파이썬
출력 : 21
설명 : 19와 25는 21에 가장 가까운 두 숫자이고 19는 21보다 작거나 같은 값을 갖는 가장 큰 숫자입니다.
입력:
출력 : 3
설명 : 3과 5는 4에 가장 가까운 두 수이고, 3은 4보다 작거나 같은 값을 갖는 가장 큰 수입니다.
목차
[순진한 접근 방식] 재귀 사용 - O(h) 시간 및 O(h) 공간
C++아이디어는 다음부터 시작하는 것입니다. 뿌리 그리고 그 값을 k와 비교합니다. 노드의 값이 k보다 크면 왼쪽 하위 트리로 이동합니다. 그렇지 않으면 k보다 작은 가장 큰 숫자의 값을 찾으십시오. 오른쪽 하위 트리 . 오른쪽 하위 트리가 -1을 반환하면(해당 값이 없음을 의미) 현재 노드의 값을 반환합니다. 그렇지 않으면 오른쪽 하위 트리에서 반환된 값을 반환합니다(현재 노드의 값보다 크지만 k보다 작기 때문입니다).
// C++ code to find the largest value // smaller than or equal to k using recursion #include
// Java code to find the largest value // smaller than or equal to k using recursion class Node { int data; Node left right; Node(int val) { data = val; left = null; right = null; } } class GfG { // function to find max value less than k static int findMaxFork(Node root int k) { // Base cases if (root == null) return -1; if (root.data == k) return k; // If root's value is smaller // try in right subtree else if (root.data < k) { int x = findMaxFork(root.right k); if (x == -1) return root.data; else return x; } // If root's data is greater // return value from left subtree. return findMaxFork(root.left k); } public static void main(String[] args) { int k = 24; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 Node root = new Node(5); root.left = new Node(2); root.left.left = new Node(1); root.left.right = new Node(3); root.right = new Node(12); root.right.left = new Node(9); root.right.right = new Node(21); root.right.right.left = new Node(19); root.right.right.right = new Node(25); System.out.println(findMaxFork(root k)); } }
# Python code to find the largest value # smaller than or equal to k using recursion class Node: def __init__(self val): self.data = val self.left = None self.right = None # function to find max value less than k def findMaxFork(root k): # Base cases if root is None: return -1 if root.data == k: return k # If root's value is smaller # try in right subtree elif root.data < k: x = findMaxFork(root.right k) if x == -1: return root.data else: return x # If root's data is greater # return value from left subtree. return findMaxFork(root.left k) if __name__ == '__main__': k = 24 # creating following BST # # 5 # / # 2 12 # / / # 1 3 9 21 # / # 19 25 root = Node(5) root.left = Node(2) root.left.left = Node(1) root.left.right = Node(3) root.right = Node(12) root.right.left = Node(9) root.right.right = Node(21) root.right.right.left = Node(19) root.right.right.right = Node(25) print(findMaxFork(root k))
// C# code to find the largest value // smaller than or equal to k using recursion using System; class Node { public int data; public Node left right; public Node(int val) { data = val; left = null; right = null; } } class GfG { // function to find max value less than k static int FindMaxFork(Node root int k) { // Base cases if (root == null) return -1; if (root.data == k) return k; // If root's value is smaller // try in right subtree else if (root.data < k) { int x = FindMaxFork(root.right k); if (x == -1) return root.data; else return x; } // If root's data is greater // return value from left subtree. return FindMaxFork(root.left k); } static void Main() { int k = 24; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 Node root = new Node(5); root.left = new Node(2); root.left.left = new Node(1); root.left.right = new Node(3); root.right = new Node(12); root.right.left = new Node(9); root.right.right = new Node(21); root.right.right.left = new Node(19); root.right.right.right = new Node(25); Console.WriteLine(FindMaxFork(root k)); } }
// JavaScript code to find the largest value // smaller than or equal to k using recursion class Node { constructor(val) { this.data = val; this.left = null; this.right = null; } } // function to find max value less than k function findMaxFork(root k) { // Base cases if (root === null) return -1; if (root.data === k) return k; // If root's value is smaller // try in right subtree else if (root.data < k) { let x = findMaxFork(root.right k); if (x === -1) return root.data; else return x; } // If root's data is greater // return value from left subtree. return findMaxFork(root.left k); } let k = 24; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 let root = new Node(5); root.left = new Node(2); root.left.left = new Node(1); root.left.right = new Node(3); root.right = new Node(12); root.right.left = new Node(9); root.right.right = new Node(21); root.right.right.left = new Node(19); root.right.right.right = new Node(25); console.log(findMaxFork(root k));
산출
21
[예상 접근 방식] Iteration을 활용 - O(h) 시간과 O(1) 공간
C++아이디어는 다음부터 시작하는 것입니다. 뿌리 그리고 그 값을 다음과 비교해보세요. 케이 . 노드의 값이 다음과 같은 경우 <= k 결과 값을 루트 값으로 업데이트하고 오른쪽 그렇지 않으면 하위 트리로 이동합니다. 왼쪽 하위 트리. 에 의해 반복적으로 모든 노드에 이 작업을 적용하면 필요한 공간을 최소화할 수 있습니다. 재귀 스택.
나무를 펴다
// C++ code to find the largest value // smaller than or equal to k using recursion #include
// Java code to find the largest value // smaller than or equal to k using recursion class Node { int data; Node left right; Node(int val) { data = val; left = null; right = null; } } class GfG { // function to find max value less than k static int findMaxFork(Node root int k) { int result = -1; // Start from root and keep looking for larger while (root != null) { // If root is smaller go to right side if (root.data <= k) { result = root.data; root = root.right; } // If root is greater go to left side else { root = root.left; } } return result; } public static void main(String[] args) { int k = 24; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 Node root = new Node(5); root.left = new Node(2); root.left.left = new Node(1); root.left.right = new Node(3); root.right = new Node(12); root.right.left = new Node(9); root.right.right = new Node(21); root.right.right.left = new Node(19); root.right.right.right = new Node(25); System.out.println(findMaxFork(root k)); } }
# Python code to find the largest value # smaller than or equal to k using recursion class Node: def __init__(self val): self.data = val self.left = None self.right = None # function to find max value less than k def findMaxFork(root k): result = -1 # Start from root and keep looking for larger while root is not None: # If root is smaller go to right side if root.data <= k: result = root.data root = root.right # If root is greater go to left side else: root = root.left return result if __name__ == '__main__': k = 24 # creating following BST # # 5 # / # 2 12 # / / # 1 3 9 21 # / # 19 25 root = Node(5) root.left = Node(2) root.left.left = Node(1) root.left.right = Node(3) root.right = Node(12) root.right.left = Node(9) root.right.right = Node(21) root.right.right.left = Node(19) root.right.right.right = Node(25) print(findMaxFork(root k))
// C# code to find the largest value // smaller than or equal to k using recursion using System; class Node { public int data; public Node left right; public Node(int val) { data = val; left = null; right = null; } } class GfG { // function to find max value less than k static int FindMaxFork(Node root int k) { int result = -1; // Start from root and keep looking for larger while (root != null) { // If root is smaller go to right side if (root.data <= k) { result = root.data; root = root.right; } // If root is greater go to left side else { root = root.left; } } return result; } static void Main() { int k = 24; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 Node root = new Node(5); root.left = new Node(2); root.left.left = new Node(1); root.left.right = new Node(3); root.right = new Node(12); root.right.left = new Node(9); root.right.right = new Node(21); root.right.right.left = new Node(19); root.right.right.right = new Node(25); Console.WriteLine(FindMaxFork(root k)); } }
// JavaScript code to find the largest value // smaller than or equal to k using recursion class Node { constructor(val) { this.data = val; this.left = null; this.right = null; } } // function to find max value less than k function findMaxFork(root k) { let result = -1; // Start from root and keep looking for larger while (root !== null) { // If root is smaller go to right side if (root.data <= k) { result = root.data; root = root.right; } // If root is greater go to left side else { root = root.left; } } return result; } let k = 24; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 let root = new Node(5); root.left = new Node(2); root.left.left = new Node(1); root.left.right = new Node(3); root.right = new Node(12); root.right.left = new Node(9); root.right.right = new Node(21); root.right.right.left = new Node(19); root.right.right.right = new Node(25); console.log(findMaxFork(root k));
산출
21퀴즈 만들기