Leetcode143: Convert Sorted List to Binary Search Tree

本文主要是介绍Leetcode143: 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 a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* createTree(vector<int> &a, int left, int right){if(left>right)  return NULL;int mid = (left+right)/2;TreeNode *node = new TreeNode(a[mid]);TreeNode *Tleft = createTree(a, left, mid-1);TreeNode *Tright = createTree(a, mid+1, right);node->left = Tleft;node->right = Tright;return node;}TreeNode* sortedListToBST(ListNode* head) {vector<int> a;ListNode *ptr = head;while(ptr){a.push_back(ptr->val);ptr = ptr->next;}return createTree(a, 0, a.size()-1);}
};

这篇关于Leetcode143: Convert Sorted List to Binary Search Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---