מריה בוטוסוב

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

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

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

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

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

//first solution
public TreeNode SortedListToBST(ListNode head) {
    List<int> arr = new List<int>();
    while(head!=null) {
        arr.Add(head.val);
        head = head.next;
    }
    
    int[] tree = arr.ToArray();
    int start = 0;
    int end = tree.Length-1;
    
    return  BST(start,end,tree);
}
 
public TreeNode BST(int start, int end, int[] tree) {
    if(start>end) return null;
    
    int mid = (start+end)/2;
    TreeNode node = new TreeNode(tree[mid]);
    node.left = BST(start,mid-1,tree);
    node.right = BST(mid+1,end,tree);
    
    return node;
}
 
//solution 2
public TreeNode SortedListToBST(ListNode head) {
    if(head == null) return null;
    if(head.next == null) return new TreeNode(head.val);
        
    ListNode fast = head;
    ListNode slow = head;
    ListNode prev = null;
        
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        prev = slow;
        slow = slow.next;
    }
    
    TreeNode curr = new TreeNode(slow.val);
    prev.next = null;
    curr.left = SortedListToBST(head);
    curr.right = SortedListToBST(slow.next);
            
    return curr;        
}