nikunjsoni

109

Mar 21st, 2021
95
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. /**
  12.  * Definition for a binary tree node.
  13.  * struct TreeNode {
  14.  *     int val;
  15.  *     TreeNode *left;
  16.  *     TreeNode *right;
  17.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  18.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  19.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  20.  * };
  21.  */
  22. class Solution {
  23. public:
  24.     ListNode* ghead;
  25.     int getSize(ListNode *head){
  26.         int sz = 0;
  27.         while(head){
  28.             sz++;
  29.             head = head->next;
  30.         }
  31.         return sz;
  32.     }
  33.    
  34.     TreeNode* convertListToBST(int l, int r){
  35.         if(l > r) return NULL;
  36.        
  37.         int mid = (l+r)>>1;
  38.         // Left node.
  39.         TreeNode *left = convertListToBST(l, mid-1);
  40.        
  41.         // Middle node.
  42.         TreeNode *node = new TreeNode(ghead->val);
  43.         ghead = ghead->next;
  44.        
  45.         //Right node.
  46.         TreeNode *right = convertListToBST(mid+1, r);
  47.        
  48.         //Assign left, right and return node.
  49.         node->left = left;
  50.         node->right = right;
  51.         return node;
  52.     }
  53.    
  54.     TreeNode* sortedListToBST(ListNode* head) {
  55.         int sz = getSize(head);
  56.         ghead = head;
  57.         return convertListToBST(0, sz-1);
  58.     }
  59. };
RAW Paste Data