LeetCode: Convert Sorted List to Binary Search Tree

Problem:

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Subscribe to see which companies asked this question

Solution:二分查找的运用

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 /**
10  * Definition for a binary tree node.
11  * struct TreeNode {
12  *     int val;
13  *     TreeNode *left;
14  *     TreeNode *right;
15  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
16  * };
17  */
18 class Solution {
19 public:
20     TreeNode* sortedListToBST(ListNode* head) {
21         
22         int length=calLength(head);
23         return createBST(0,length-1,head);
24         
25         
26         
27     }
28     //二分构建二叉查找树
29     TreeNode* createBST(int left,int right,ListNode *p)
30     {
31         if(right<left) return NULL;
32         
33         int middle=(left+right)/2;
34         
35         ListNode *node=p;
36         for(int i=left;i<middle;i++)
37             node=node->next;
38         TreeNode *root=new TreeNode(node->val);
39         TreeNode *leftnode=createBST(left,middle-1,p);
40         TreeNode *rightnode=createBST(middle+1,right,node->next);
41         root->left=leftnode;
42         root->right=rightnode;
43         return root;
44         
45     }
46     
47     //计算链表长度
48     int calLength(ListNode *p)
49     {
50         int len=0;
51         while(p)
52         {
53             len++;
54             p=p->next;
55         }
56         return len;
57     }
58     
59 };