Alibi

My Life is Getting Better

Leetcode[108, 109] Convert Sorted Array/list to Binary Search Tree

08 Nov 2015

###Task1 Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

###Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return None
        length = len(nums)
        if length == 0:
            return None
        mid = length / 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid + 1:])
        return root

###Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

	public TreeNode bstHelper(int[] nums, int start, int end) {
		if (start == end) {
			return new TreeNode(nums[start]);
		}
		if (start > end) {
			return null;
		}
		int mid = start + (end - start) / 2;
		TreeNode cur = new TreeNode(nums[mid]);
		cur.left = bstHelper(nums, start, mid - 1);
		cur.right = bstHelper(nums, mid + 1, end);

		return cur;
	}

    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
        	return null;
        }

        return bstHelper(nums, 0, nums.length - 1);
    }
}

###Points

###Task2 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. ###Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)
        midPrev = self.findMid(head)
        root = TreeNode(midPrev.next.val)
        root.right = self.sortedListToBST(midPrev.next.next)
        midPrev.next = None
        root.left = self.sortedListToBST(head)
        return root
    def findMid(self, head):
        prev = None
        slow = head
        fast = head.next
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        return prev if prev != None else slow

###Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode findMid(ListNode head) {
        ListNode prev = null;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        return prev != null ? prev : slow;
    }
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        ListNode preMid = findMid(head);
        ListNode mid = preMid.next;
        preMid.next = null;
        TreeNode left = sortedListToBST(head);
        TreeNode right = sortedListToBST(mid.next);
        TreeNode root = new TreeNode(mid.val);
        root.left = left;
        root.right = right;
        
        return root;
    }
}

###Points

Related Posts