C++ solution .....


  • -1
    L

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • ListNode *next;
      
    • ListNode(int x) : val(x), next(NULL) {}
      
    • };
      /
      /
      *

    • Definition for a binary tree node.

    • struct TreeNode {

    • int val;
      
    • TreeNode *left;
      
    • TreeNode *right;
      
    • TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      
    • };
      */
      class Solution {
      public:

      TreeNode* convertArrayToBST(vector<ListNode*>& listNodes, int start, int end) {
      int middle = (start + end)/2;

       TreeNode* root = new TreeNode(listNodes[middle]->val);
       
       if ((middle - 1) >= start) {
           root->left = convertArrayToBST(listNodes, start, middle-1);
       }
           
       if ((middle + 1) <= end) {
           root->right = convertArrayToBST(listNodes, middle+1, end);
       }
       return root;
      

      }

      TreeNode* sortedListToBST(ListNode* head) {

       if (head == NULL) {
           return NULL;
       }
       
       vector<ListNode*> listNodes;
       while (head) {
           listNodes.push_back(head);
           head = head->next;
       }
       
       return convertArrayToBST(listNodes, 0, listNodes.size()-1);
      

      }
      };


Log in to reply
 

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