leetcode Convert Sorted List to Binary Search Tree

13-10-17 来源：[db:作者]

收藏我要投稿

The problem is quite interesting when limiting memory to O(1), and time complexity to O(n). In that way, extra array is forbidden. So

When there is only one node A, mid = A, NULL<-mid->NULL

When there are two node A, A+1, mid = A, NULL<-mid->A+1

When there are three node A, A+1, A+2, mid = A+1, A<-A+1->A+2

....

After building the tree, the pointer moves to the end. The code is like:

/** 
 * Definition for singly-linked list. 
 * struct ListNode { 
 *     int val; 
 *     ListNode *next; 
 *     ListNode(int x) : val(x), next(NULL) {} 
 * }; 
 */  
/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */  
class Solution {  
 public:  
  TreeNode* BuildTree(ListNode*& head, int start, int end) {  
      if (start > end)   
        return NULL;  
      int mid = start + (end - start) / 2;  
        
      TreeNode* lChild = BuildTree(head, start, mid - 1);  
      TreeNode* parent = new TreeNode(head->val);  
      parent->left = lChild;  
      head = head->next;  
      TreeNode* rChild = BuildTree(head, mid + 1, end);  
      parent->right = rChild;  
      return parent;  
  }  
  TreeNode *sortedListToBST(ListNode *head) {  
    // Note: The Solution object is instantiated only once and is reused by each test case.  
    ListNode* p = head;  
    int len = 0;   
    while (p != NULL) {  
        len++;  
        p = p->next;  
    }  
    return BuildTree(head, 0, len-1);  
  }  
};

I once wrote the function like:

TreeNode* BuildTree(ListNode* head, int start, int end)  
which got wrong answer.

点击复制链接与好友分享!回本站首页