Share quite long java solution but no recursive, O(n) time and O(log(n)) space complexity


  • 0
    D
    public TreeNode sortedListToBST(ListNode head) {
            if(head == null){
                return null;
            }
            // count number of nodes
            int count = 0;
            ListNode ptr = head;
            while(ptr != null){
                count++;
                ptr = ptr.next;
            }
            // build balanced tree
            Stack<TreeNode> st = new Stack<TreeNode>();
            Stack<Integer> nbNodesNeeded = new Stack<Integer>();
            TreeNode res = new TreeNode(0);
            st.push(res);
            nbNodesNeeded.push(count);
            while(!st.isEmpty()){
                count = nbNodesNeeded.pop() - 1;
                TreeNode root = st.pop();
                if(count == 0){
                    continue;
                }
                if(count == 1){
                    root.left = new TreeNode(0);
                    continue;
                }
                if(count == 2){
                    root.left = new TreeNode(0);
                    root.right = new TreeNode(0);
                    continue;
                }
               
                
                root.right = new TreeNode(0);
                st.push(root.right);
                int rightCount = count /2 ;
                nbNodesNeeded.push(rightCount);
                
                root.left = new TreeNode(0);
                st.push(root.left);
                int leftCount = count - rightCount;
                nbNodesNeeded.push(leftCount);
           }
           
           // inorder traversal to put values
           st.push(res);
           TreeNode current = res.left;
           while(!st.isEmpty() || current != null){
               while(current != null){
                   st.push(current);
                   current = current.left;
               }
               current = st.pop();
               current.val = head.val;
               head = head.next;
               current = current.right;
           }
           return res;
            
        }

Log in to reply
 

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