LeetCode: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) {}
* };
*/
class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &num) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int len = num.size();
if(len == )return NULL;
return sortedArrayToBSTRecur(num, , len-);
}
TreeNode *sortedArrayToBSTRecur(vector<int> &num, int istart, int iend)
{
if(istart > iend)return NULL;
int middle = (istart+iend)/;
TreeNode *res = new TreeNode(num[middle]);
res->left = sortedArrayToBSTRecur(num, istart, middle-);
res->right = sortedArrayToBSTRecur(num, middle+, iend);
return res;
}
};
LeetCode: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) {}
* };
*/
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if(head == NULL)return NULL;
ListNode *fast = head, *slow = head, *preSlow = NULL;
while(fast->next && fast->next->next)
{
fast = fast->next->next;
preSlow = slow;
slow = slow->next;
}
TreeNode *res = new TreeNode(slow->val);
fast = slow->next;
delete slow;
if(preSlow != NULL)
{
preSlow->next = NULL;
res->left = sortedListToBST(head);
}
res->right = sortedListToBST(fast);
return res;
}
};
【版权声明】转载请注明出处：http://www.cnblogs.com/TenosDoIt/p/3440079.html