- Leetcode 108. Convert Sorted Array to Binary Search Tree
- Leetcode 109. Convert Sorted List to Binary Search Tree
Binary Search Tree
Leetcode 108. Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size()-1);
}
TreeNode* helper(vector<int> &nums, int i, int j) {
if (i>j) return NULL;
int mid = i+(j-i)/2;
TreeNode* node = new TreeNode(nums[mid]);
node->left = helper(nums, i, mid-1);
node->right = helper(nums, mid+1, j);
return node;
}
};
Leetcode 109. 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.
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if (!head) return NULL;
if (!head->next) return new TreeNode(head->val);
ListNode* slow = head;
ListNode* fast = head;
ListNode* tail = NULL;
while (fast && fast->next) {
tail = slow;
slow = slow->next;
fast = fast->next->next;
}
tail->next = NULL;
TreeNode* node = new TreeNode(slow->val);
node->left = sortedListToBST(head);
node->right = sortedListToBST(slow->next);
return node;
}
};