LC: 272. Closest Binary Search Tree Value II
https://leetcode.com/problems/closest-binary-search-tree-value-ii/
272. Closest Binary Search Tree Value II
Given the root of a binary search tree, a target value, and an integer k, return the k values in the BST that are closest to the target. You may return the answer in any order.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example 1:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4,3]Example 2:
Input: root = [1], target = 0.000000, k = 1
Output: [1]Constraints:
The number of nodes in the tree is
n.1 <= k <= n <= 104.0 <= Node.val <= 109-109 <= target <= 109
Follow up: Assume that the BST is balanced. Could you solve it in less than O(n) runtime (where n = total nodes)?
272. Closest Binary Search Tree Value II:
The Essence: Wenn man einen binären Suchbaum in symmetrischer Reihenfolge (L-N-R) traversiert, ist die Reihe der verarbeiteten Knoten sortiert. Wir nehmen an, dass die Rückgabe-Liste zuerst aus den kleinsten Werten besteht. Wenn ein größerer, aber in Differenz kleiner Wert begegnet wird, soll der Kopf der Liste gelöscht und der neue Wert am Ende zugefügt werden. Der Kopf wird gelöscht, da es am fernsten von dem Zielwert würde.
Details:
Es ist effizienter, wenn man für die Liste eine verkettete Liste, bei welcher der Kopfknoten zur Verfügung steht, verwendet. Außerdem kann die “in-order” Traversierung des Baums rekursiv implementiert werden.
Solutions:
You can find the detailed explanation here: https://github.com/spiralgo/algorithms/pull/299
Default Code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
}
}Last updated