Advertisement
Guest User

Untitled

a guest
May 27th, 2019
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.86 KB | None | 0 0
  1. /**
  2. this method is also worst case O(N), however, if BST is balanced, this would be O(K + lgN)
  3. */
  4. public List<Integer> closestKValues(TreeNode root, double target, int k) {
  5. List<Integer> res = new ArrayList<>();
  6.  
  7. Stack<Integer> predecessors = new Stack<>();
  8. Stack<Integer> successors = new Stack<>();
  9.  
  10. this.traverseTreeInorder(root, target, predecessors);
  11. this.traverseTreeReverseInorder(root, target, successors);
  12.  
  13. while (k > 0) {
  14. if (predecessors.empty()) {
  15. res.add(successors.pop());
  16. } else if (successors.empty()) {
  17. res.add(predecessors.pop());
  18. } else if (Math.abs(predecessors.peek() - target) < Math.abs(successors.peek() - target)) {
  19. res.add(predecessors.pop());
  20. } else {
  21. res.add(successors.pop());
  22. }
  23.  
  24. k--;
  25. }
  26.  
  27. return res;
  28. }
  29.  
  30. private void traverseTreeInorder(TreeNode node, double target, Stack<Integer> predecessor) {
  31. if (node == null) {
  32. return;
  33. }
  34.  
  35. this.traverseTreeInorder(node.left, target, predecessor);
  36.  
  37. // have to exclude at least once from either methods traverseTreeInorder or traverseTreeReverseInorder to avoid
  38. // duplicates
  39. if (node.val >= target) {
  40. return;
  41. }
  42.  
  43. predecessor.push(node.val);
  44.  
  45. this.traverseTreeInorder(node.right, target, predecessor);
  46.  
  47. }
  48.  
  49. private void traverseTreeReverseInorder(TreeNode node, double target, Stack<Integer> successor) {
  50. if (node == null) {
  51. return;
  52. }
  53.  
  54. this.traverseTreeReverseInorder(node.right, target, successor);
  55.  
  56. if (node.val < target) {
  57. return;
  58. }
  59.  
  60. successor.push(node.val);
  61.  
  62. this.traverseTreeReverseInorder(node.left, target, successor);
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement