Please help me figure out why my recursive code is wrong


  • 0
    Q
    public class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            //recursive DAC
            if(head == null) return null;
            if(head.next == null) return new TreeNode(head.val);
            int length = 0;
            ListNode cur = head;
            //find the length of the list
            if(cur != null){
                length++;
                cur = cur.next;
            }
            //find the node points to mid 
            cur = head;
            for(int i = 0; i < (length / 2 - 1); i++){
                cur = cur.next;
            }
            ListNode mid = cur.next;
            TreeNode root = new TreeNode(mid.val);
            //divide the list into two parts, secHead is the head of the right list
            cur.next = null;
            ListNode secHead = mid.next;
            mid.next = null;
            root.left = sortedListToBST(head);
            root.right = sortedListToBST(secHead);
            return root;
        }
    }

  • 0
    D

    Your algorithm is fine, except it is time-consuming. It is Olog(n). The following algorithm should run in O(n).

    Yes, at first it's hard to see whether it is O(n), but study it and you can see ^_^

    public class Solution {
        
        public TreeNode sortedListToBST(ListNode head) {
            int count = count(head);
            Pointer p = new Pointer(head);
            return sortedListToBST(p, count);
        }
        
        public TreeNode sortedListToBST(Pointer head,int count){
            if(count <= 0) return null;
            
            TreeNode left = sortedListToBST(head, count/2);
            TreeNode root = new TreeNode(head.current.val);
            root.left = left;
            head.current = head.current.next;
            TreeNode right = sortedListToBST(head, count-1-count/2);
            root.right = right;
            return root;
        }
        
        private int count(ListNode head){
            int count = 0;
            while(head!=null){
                count++;
                head = head.next;
            }
            return count;
        }
        
        private class Pointer {
            ListNode current;
            public Pointer(ListNode head){
                current = head;
            }
        }
    }

  • 0
    Q

    Thank you for your answer, your solution is good, and now I know my solution calculates the length of LinkedList repeatly thus it is TLE. For your solution, I think using a new class to wrap the ListNode is useless.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.