Advertisement
unknown_0711

Untitled

Dec 24th, 2022
17
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.10 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. class Node {
  4. int data;
  5. Node left, right;
  6.  
  7. public Node(int item) {
  8. data = item;
  9. left = right = null;
  10. }
  11. }
  12.  
  13. class BinarySearchTree {
  14. Node constructBST(int[] arr, int start, int end, Node root) {
  15. if (start > end)
  16. return null;
  17. int mid = (start + end) / 2;
  18.  
  19. if (root == null)
  20. root = new Node(arr[mid]);
  21.  
  22. root.left = constructBST(arr, start, mid - 1, root.left);
  23. root.right = constructBST(arr, mid + 1, end, root.right);
  24.  
  25. return root;
  26.  
  27. }
  28. }
  29.  
  30. public class Main {
  31. public static void main(String[] args) throws Throwable {
  32. Scanner sc = new Scanner(System.in);
  33. int n = sc.nextInt();
  34. int arr[] = new int[n];
  35. for (int i = 0; i < n; i++) {
  36. arr[i] = sc.nextInt();
  37. }
  38. int target = sc.nextInt();
  39. Arrays.sort(arr);
  40. Node root = null;
  41. BinarySearchTree bst = new BinarySearchTree();
  42. root = bst.constructBST(arr, 0, n - 1, root);
  43. Accio A = new Accio();
  44. A.targetSum(root, target);
  45. sc.close();
  46. }
  47. }
  48. class Accio {
  49. boolean t=false;
  50. public boolean find(Node node, int data) {
  51. if (node == null) {
  52. return false;
  53. }
  54. if (data > node.data) {
  55. return find(node.right, data);
  56. } else if (data < node.data) {
  57. return find(node.left, data);
  58. } else {
  59. return true;
  60. }
  61. }
  62. public void targetSumPair(Node root, Node node, int tar) {
  63. if (node == null) {
  64. return;
  65. }
  66. targetSumPair(root, node.left, tar);
  67. int comp = tar - node.data;
  68. if (comp > node.data) {
  69. if (find(root, comp)) {
  70. t=true;
  71. System.out.println(node.data + " " + comp);
  72. }
  73. }
  74. targetSumPair(root, node.right, tar);
  75. }
  76. public void targetSum(Node root, int tar)
  77. {
  78. targetSumPair(root, root, tar);
  79. if(t==false)
  80. System.out.println(-1);
  81. }
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement