Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- this method is also worst case O(N), however, if BST is balanced, this would be O(K + lgN)
- */
- public List<Integer> closestKValues(TreeNode root, double target, int k) {
- List<Integer> res = new ArrayList<>();
- Stack<Integer> predecessors = new Stack<>();
- Stack<Integer> successors = new Stack<>();
- this.traverseTreeInorder(root, target, predecessors);
- this.traverseTreeReverseInorder(root, target, successors);
- while (k > 0) {
- if (predecessors.empty()) {
- res.add(successors.pop());
- } else if (successors.empty()) {
- res.add(predecessors.pop());
- } else if (Math.abs(predecessors.peek() - target) < Math.abs(successors.peek() - target)) {
- res.add(predecessors.pop());
- } else {
- res.add(successors.pop());
- }
- k--;
- }
- return res;
- }
- private void traverseTreeInorder(TreeNode node, double target, Stack<Integer> predecessor) {
- if (node == null) {
- return;
- }
- this.traverseTreeInorder(node.left, target, predecessor);
- // have to exclude at least once from either methods traverseTreeInorder or traverseTreeReverseInorder to avoid
- // duplicates
- if (node.val >= target) {
- return;
- }
- predecessor.push(node.val);
- this.traverseTreeInorder(node.right, target, predecessor);
- }
- private void traverseTreeReverseInorder(TreeNode node, double target, Stack<Integer> successor) {
- if (node == null) {
- return;
- }
- this.traverseTreeReverseInorder(node.right, target, successor);
- if (node.val < target) {
- return;
- }
- successor.push(node.val);
- this.traverseTreeReverseInorder(node.left, target, successor);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement