OJ: https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
思想： 以中间点为根节点，按先序顺序来创建 。
/**
* 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) {}
* };
*/
ListNode* findMiddleNode(ListNode *head, int length) {
if(length <= 0) return NULL;
int mid = (length+1) / 2;
for(int i = 1; i < mid; ++i) head = head->next;
return head;
}
TreeNode* createBST(ListNode *head, int length) {
ListNode *pMid = findMiddleNode(head, length);
TreeNode *root = NULL;
if(pMid) {
root = new TreeNode(pMid->val);
root->left = createBST(head, (length-1) >> 1);
root->right = createBST(pMid->next, length / 2);
}
return root;
}
int getLength(ListNode *head) {
int len = 0;
while(head) { len++; head = head->next; }
return len;
}
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
return createBST(head, getLength(head));
}
};
OJ: https://oj.leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
思想，同上。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
TreeNode* createBST(vector<int> &num, int l, int h) {
if(l > h) return NULL;
int mid = (l+h)/2;
TreeNode *root = new TreeNode(num[mid]);
root->left = createBST(num, l, mid-1);
root->right = createBST(num, mid+1, h);
return root;
}
class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &num) {
return createBST(num, 0, num.size()-1);
}
};
34. Convert Sorted List to Binary Search Tree && Convert Sorted Array to Binary Search Tree
原文：http://www.cnblogs.com/liyangguang1988/p/3939909.html