C# Without finding mid root node - Accepted


  • 1
    S

    Technique here is use the same logic how we do if the input is sorted array.

    public class Solution {

        ListNode listNode;
    
        public TreeNode SortedListToBST(ListNode head) {
        
            if(head == null)
                return null;
            if(head !=null && head.next == null)
                return new TreeNode(head.val);
                
            int listLen = GetSLLLen(head);
            listNode = head;
            TreeNode treeNode = createTreeFromSLL(1, listLen);
            return treeNode;
        }
    
        public int GetSLLLen(ListNode rootNode)
        {
            int len = 0;
            
            ListNode currentNode = rootNode;
    
            while (currentNode != null)
            {
                len++;
                currentNode = currentNode.next;
            }
            return len;
        }
    
        public TreeNode createTreeFromSLL(int leftPos, int rightPos)
        {
            if (leftPos > rightPos) // Creation done.
                return null;
    
            int mid = (leftPos + (rightPos - leftPos) / 2);
    
            // Mid Creation
            TreeNode parentNode = new TreeNode(0);
    
            // Left side exclude mid.
            parentNode.left = createTreeFromSLL(leftPos, mid - 1);
            parentNode.val = listNode.val;
    
            listNode = listNode.next;
            // Right side exclude mid.
            parentNode.right = createTreeFromSLL(mid + 1, rightPos);
            return parentNode;
        }       
    

    }


Log in to reply
 

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