Description

LeetCode 109

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Analysis

A direct solution is to set the middle element as the root and set the left list as the left subtree and the right list as the right subtree. The given list is a linked list so we have to find the element with \(O(n)\) time instead of \(O(1)\) time. So this solution needs \(O(nlogn)\) time. In this solution, the nodes has been visited for more than once. We should consider how to visit the nodes once to make the solution consistent with the feature of linked list.

If we want to use the advantages of linked list, we should visit the nodes from head to tail. The sequence is like an inorder traversal. And the left subtree and the right subtree are divided by the middle element.

The code is also skillful. We should set a global tree node variable whose initial value is the head of the linked list. And when the variable is visited, set it to the next. And the recursive process can be described as three steps. The first step is constructing the left subtree recursively. The second step is constructing a root whose value is the global tree node’s value now and set the left node of root to the left subtree. The third step is set the right subtree recursively.

We can just visit the nodes once. So the time is \(O(n)\).

Solution

/**
 * 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; }
 * }
 */
class Solution {
    ListNode h;
    public TreeNode sortedListToBST(ListNode head) {
        ListNode p=head;
        int cnt=0;
        while(p!=null)
        {
            p=p.next;
            cnt++;
        }
        h=head;
        return helper(cnt);
    }
    public TreeNode helper(int n)
    {
        if(n<=0) return null;
        TreeNode left=helper(n/2);
        TreeNode root=new TreeNode(h.val);
        root.left=left;
        h=h.next;
        root.right=helper(n-1-n/2);
        return root;
    }
}

Reference

[1] https://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/

Leave a Reply

Your email address will not be published. Required fields are marked *