Leetcode/Airbnb -- 108.109. Convert Sorted Array to Binary Search Tree(dfs)

108. Convert Sorted Array to Binary Search Tree(dfs)

• Difficulty: Medium

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Company: Airbnb

思路： Constructing from sorted array in O(n) time is simpler as we can get the middle element in O(1) time.

1) Get the Middle of the array and make it root.
2) Recursively do same for left half and right half.
      a) Get the middle of left half and make it left child of the root
          created in step 1.
      b) Get the middle of right half and make it right child of the
          root created in step 1.

Time Complexity: O(n)-- O(n) to build tree and get middle at O(1) T(n) = 2T(n/2) + O(1)

Following is the recurrance relation for sortedArrayToBST().

  T(n) = 2T(n/2) + C
  T(n) -->  Time taken for an array of size n
   C   -->  Constant (Finding middle of array and linking root to left 
                      and right subtrees take constant time) 

 eg: [0,1,5,7,6], print order: 5,0,1,7,6

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        TreeNode head = helper(nums, 0, nums.length - 1);
        return head;
    }
    public TreeNode helper(int[] nums,int low, int high){
        if(low>high) return null;
        int mid = low + (high-low)/2;
        TreeNode node = new TreeNode(nums[mid]);//Get the middle element and make it root
        node.left = helper(nums,low,mid-1);//recur construct left subtree !mid is added, so mid-1
        node.right = helper(nums,mid+1,high);
        return node;
    }
}

109. Convert Sorted List to Binary Search Tree

思路： process same as array - find the middle of list.
            Return case: start == end
Complexity: Time O(nlogn) - O(n) nodes to build, each time O(lgn) to find the middle of  List
                      Space O(1)

public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)return null;
        TreeNode root = buildTree(head, null);
        return root;
    }
    public TreeNode buildTree(ListNode start, ListNode end){
        if(start == end)return null;
        ListNode fast = start;
        ListNode slow =  start;
        while(fast != end && fast.next != end){
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = buildTree(start, slow);
        root.right = buildTree(slow.next, end);
        return root;
    }
}