מאי.15

להמיר רשימה מקושרת ממוינת לעץ חיפוש בינארי

להמיר רשימה מקושרת ממוינת לעץ חיפוש בינארי

יש להמיר רשימה מקושרת ממוינת לעץ חיפוש בינארי. חשוב שעץ יהיה מאוזן בגובה (הבדל בין עומק של כל תת עץ יהיה מקסימום 1).

בגלל שאנחנו צריכים לבנות עץ מאוזן מרשימה מקושרת ממוינת - אנחנו בכל מקרה צריכים למצוא עמצא של רשימה מקושרת.

יש 2 דרכים לפתרון:

 - יותר מהיר ע''י שימוש של רשימה של כל הערכים

- יותר אלגנטי ע''י שימוש של מצביעה מהיר ואיטי


  1. //first solution
  2. public TreeNode SortedListToBST(ListNode head) {
  3. List<int> arr = new List<int>();
  4. while(head!=null) {
  5. arr.Add(head.val);
  6. head = head.next;
  7. }
  8. int[] tree = arr.ToArray();
  9. int start = 0;
  10. int end = tree.Length-1;
  11. return BST(start,end,tree);
  12. }
  13.  
  14. public TreeNode BST(int start, int end, int[] tree) {
  15. if(start>end) return null;
  16. int mid = (start+end)/2;
  17. TreeNode node = new TreeNode(tree[mid]);
  18. node.left = BST(start,mid-1,tree);
  19. node.right = BST(mid+1,end,tree);
  20. return node;
  21. }
  22.  
  23. //solution 2
  24. public TreeNode SortedListToBST(ListNode head) {
  25. if(head == null) return null;
  26. if(head.next == null) return new TreeNode(head.val);
  27. ListNode fast = head;
  28. ListNode slow = head;
  29. ListNode prev = null;
  30. while(fast != null && fast.next != null){
  31. fast = fast.next.next;
  32. prev = slow;
  33. slow = slow.next;
  34. }
  35. TreeNode curr = new TreeNode(slow.val);
  36. prev.next = null;
  37. curr.left = SortedListToBST(head);
  38. curr.right = SortedListToBST(slow.next);
  39. return curr;
  40. }


תגיות:
שתף את הסיפור הזה:

תגובות(0)

השאירו תגובה

קפטצ'ה לא מתאימה

תגובה