나는 목표에 가장 가까운있는 BST에서 K 값을 찾는 방법에 대한 연구, 그리고 규칙에 다음과 같은 구현 건너 온거야 : 비어 있지 않은 이진 검색 트리 감안할 때자바 : BST에서 타겟에 가장 가까운 k 값을 찾는 방법은 무엇입니까?
과 목표 값 , 목표에 가장 가까운 BST에서 k 값을 찾으십시오.
참고 :
감안할 때 목표 값은 부동 소수점입니다. k가 항상 유효하다고 가정 할 수 있습니다. 즉, k ≤ 총 노드입니다. BST에는 대상과 가장 가까운 k 개의 고유 한 값 집합 만있을 수 있습니다. BST가 균형 잡힌 것으로 가정합니다.
그리고 구현의 생각은 :
, 우리는 우리가하는 일처럼 전임자와 후임자를 추적하는 두 개의 스택을 사용할 수있는 대상에 전임자와 가장 가까운 노드의 후계자 비교 병합 정렬에서는 대상과 가장 가까운 것을 비교하여 결과 목록에 배치합니다. 우리가 알고 있듯이, inorder traversal은 이전의 정렬 된 것을 제공하는 반면 reverse-inorder traversal은 정렬 된 후임을 제공합니다.
코드 :
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) {
val = x;
}
}
public class ClosestBSTValueII {
List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> res = new ArrayList<>();
Stack<Integer> s1 = new Stack<>(); // predecessors
Stack<Integer> s2 = new Stack<>(); // successors
inorder(root, target, false, s1);
inorder(root, target, true, s2);
while (k-- > 0) {
if (s1.isEmpty()) {
res.add(s2.pop());
} else if (s2.isEmpty()) {
res.add(s1.pop());
} else if (Math.abs(s1.peek() - target) < Math.abs(s2.peek() - target)) {
res.add(s1.pop());
} else {
res.add(s2.pop());
}
}
return res;
}
// inorder traversal
void inorder(TreeNode root, double target, boolean reverse, Stack<Integer> stack) {
if (root == null) {
return;
}
inorder(reverse ? root.right : root.left, target, reverse, stack);
// early terminate, no need to traverse the whole tree
if ((reverse && root.val <= target) || (!reverse && root.val > target)) {
return;
}
// track the value of current node
stack.push(root.val);
inorder(reverse ? root.left : root.right, target, reverse, stack);
}
public static void main(String args[]) {
ClosestBSTValueII cv = new ClosestBSTValueII();
TreeNode root = new TreeNode(53);
root.left = new TreeNode(30);
root.left.left = new TreeNode(20);
root.left.right = new TreeNode(42);
root.right = new TreeNode(90);
root.right.right = new TreeNode(100);
System.out.println(cv.closestKValues(root, 40, 2));
}
}
그리고 내 질문에, 어떤 두 스택을 가진 이유는 그리고 방법의 순서 좋은 방법입니다? 각각의 목적은 무엇입니까? 하나의 스택으로는 충분하지 않을까요?
과 같이 reverse 부울 값은 무엇입니까? if ((reverse && root.val <= target) || (!reverse && root.val > target))의 경우 왜 일찍 해지합니까?
감사합니다. 미리 답변 해 주시고 답변을 드리겠습니다.
코드가 이미 작동하는 경우이 질문은 [코드 검토] (http://codereview.stackexchange.com) 사이트에서 더 잘 맞을 수 있습니다. –
귀하의 질문을 이해하고 있는지 확실하지 않습니다. 후임 노드를 찾으시겠습니까? 재귀 적 접근으로이를 수행 할 수 있습니다. – Baxtex
@Baxtex 나는이 접근법을 이해하려고 노력하고 있습니다. –