LeetCode OJ (C#) – Convert Sorted List to Binary Search Tree

Tags

binary Search tree, LeetCode, LinkedList, Tree And Graph

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

Solution 1: it is hard to find the mid of linked list. so convert the linked list to array and then convert array to binary search tree would be an easy way to solve this issue. please see Convert Sorted Array to Binary Search Tree.

        public TreeNode SortedListToBST(ListNode head)
        {
            var values = new List();

            while (head != null)
            {
                values.Add(head.val);
                head = head.next;
            }

            return SortedArrayToBST(values.ToArray(), 0, values.Count - 1);
        }

        private TreeNode SortedArrayToBST(int[] values, int low, int high)
        {
            if (low > high)
            {
                return null;
            }

            var mid = (high - low)/2 + low;
            var root = new TreeNode(values[mid])
            {
                left = SortedArrayToBST(values, low, mid - 1),
                right = SortedArrayToBST(values, mid + 1, high)
            };

            return root;
        }

Solution 2: solve the same way as convert array to binary search tree, find the mid of node in linked list and put it as root. put linked list to two parts, from the first part, find the mid and put it as left child of root, find the mid of right part and put it as right child of root. Use two pointers, one is slow(move one node at a time) and the other is fast (move two nodes at a time) to find the mid.

        public TreeNode sortedListToBST(ListNode head)
        {
            if (head == null)
            {
                return null;
            }

            var tail = head;
            while (tail.next != null)
            {
                tail = tail.next;
            }

            return sortedListToBSTRecursion(head, tail);
        }

        private TreeNode sortedListToBSTRecursion(ListNode head, ListNode tail)
        {
            if (head == null || tail == null || head == tail.next)
            {
                return null;
            }

            var slow = head;
            ListNode preslow = null;
            var fast = head;
            while (fast != tail && fast.next != tail)
            {
                preslow = slow;
                slow = slow.next;
                fast = fast.next.next;
            }

            var newNode = new TreeNode(slow.val);
            newNode.left = this.sortedListToBSTRecursion(head, preslow);
            newNode.right = this.sortedListToBSTRecursion(slow.next, tail);

            return newNode;
        }

Solution 3: build from bottom up instead of up bottom would reduce the time from O(nlgn) to O(n). See here for more information.

        public TreeNode SortedListToBST(ListNode head)
        {
            var k = this.GetCount(head);
            return this.SortedListToBSTHelper(ref head, k);
        }

        private TreeNode SortedListToBSTHelper(ref ListNode head, int k)
        {
            if (k <= 0)
            {
                return null;
            }

            var left = this.SortedListToBSTHelper(ref head, k / 2);

            var root = new TreeNode(head.val) { left = left };
            head = head.next;

            var right = this.SortedListToBSTHelper(ref head, k - k / 2 - 1);
            root.right = right;

            return root;
        }

        private int GetCount(ListNode head)
        {
            var count = 0;

            while (head != null)
            {
                head = head.next;
                count++;
            }

            return count;
        }