1 題目

給定一個單鏈表，其中的元素按升序排序，請將它轉(zhuǎn)化成平衡二叉搜索樹（BST）

2 解法

2.1 轉(zhuǎn)化有序鏈表為數(shù)組

/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/ /*** struct ListNode {* int val;* struct ListNode *next;* };*/class Solution { public:/*** * @param head ListNode類 * @return TreeNode類*/TreeNode* sortedListToBST(ListNode* head) {// write code hereif (!head)return nullptr;vector<int> tmpList;for (auto p = head; p; p = p->next) {tmpList.push_back(p->val);}TreeNode* res = toBST(0, tmpList.size(), tmpList);return res;}TreeNode* toBST(int start, int end, vector<int> list) {if (start >= end)return nullptr;int target_index = (start + end) / 2;TreeNode* tmp_res = new TreeNode(list[target_index]);tmp_res->left = toBST(start, target_index, list);tmp_res->right = toBST(target_index + 1, end, list);return tmp_res;} };

這么玩兒有點違背出題者初衷了

2.2 用快慢針找到鏈表中點

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的leetcode 109 --- 有序链表变成二叉搜索树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。