[Leetcode] Convert Sorted List to Binary Search Tree
2023-09-11 14:17:25 时间
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Depth-first Search Linked List
方法一:借助Convert Sorted Array to Binary Search Tree 的方法,先将list转成vector即可,时间复杂度O(n),转化过程就是O(n),空间复杂度O(n)
class Solution { public: TreeNode *sortedListToBST(ListNode *head) { vector<int> num; while(head != NULL) { num.push_back(head->val); head = head->next; } return sortedArrayToBST(num); } TreeNode *sortedArrayToBST(vector<int> &num) { int size = num.size(); if(size == 0) return NULL; return sortedArrayToBSTInternal(num, 0, size - 1); } TreeNode *sortedArrayToBSTInternal(vector<int> &num, int low, int high) { // the code is very important, i.e: low = 4, hight = 5, mid = 4, // will call sortedArrayToBSTInternal(num, 4, 3) if(low > high) return NULL; if(low == high) return new TreeNode(num[low]); int mid = (high-low)/2 + low; cout << mid << endl; TreeNode *root = new TreeNode(num[mid]); TreeNode *left = sortedArrayToBSTInternal(num, low, mid - 1); TreeNode *right = sortedArrayToBSTInternal(num, mid + 1, high); root->left = left; root->right= right; return root; } };
方法二:找出当前链表的中间节点,然后再递归左右的子链表,开始的时候程序先计算链表总厂,然后传入两个前后索引指针,最后每次递归找出中间节点即可。
时间复杂度O(n^2),空间复杂度O(logn),递归导致stack用O(logn)
/** * 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: int calLen(ListNode *node) { int len = 0; while(node) { len++; node = node->next; } return len; } TreeNode *createTree(ListNode *node, int left, int right) { if (left > right) return NULL; int mid = (left + right) / 2; ListNode *p = node; for(int i = left; i < mid; i++) p = p->next; TreeNode *leftNode = createTree(node, left, mid - 1); TreeNode *rightNode = createTree(p->next, mid + 1, right); TreeNode *tNode = new TreeNode(p->val); tNode->left = leftNode; tNode->right = rightNode; return tNode; } TreeNode *sortedListToBST(ListNode *head) { // Start typing your C/C++ solution below // DO NOT write int main() function int len = calLen(head); return createTree(head, 0, len - 1); } };
方法3:
bottom-up,时间复杂度 O(n),空间复杂度 O(logn)
http://blog.csdn.net/salutlu/article/details/24502109 中递归
http://www.bwscitech.com/a/jishuzixun/javayuyan/2013/0930/15822.html
存在一种自底向上 (bottom-up) 的方法,见 http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
class Solution { public: TreeNode *sortedListToBST(ListNode *head) { int len = 0; ListNode *p = head; while (p) { len++; p = p->next; } return sortedListToBST(head, 0, len - 1); } private: TreeNode* sortedListToBST(ListNode*& list, int start, int end) { if (start > end) return NULL; int mid = start + (end - start) / 2; TreeNode *leftChild = sortedListToBST(list, start, mid - 1); TreeNode *parent = new TreeNode(list->val); parent->left = leftChild; list = list->next; parent->right = sortedListToBST(list, mid + 1, end); return parent; } };
相关文章
- Leetcode 之Convert Sorted List to Binary Search Tree(55)
- leetcode 之Remove Duplicates from Sorted List(17)
- Java实现 LeetCode 486 预测赢家
- Java实现 LeetCode 440 字典序的第K小数字
- Java实现 LeetCode 24 两两交换链表中的节点
- Java实现LeetCode_0027_RemoveElement
- Java实现LeetCode_0028_ImplementStrStr
- (LeetCode 92)Reverse Linked List II
- (LeetCode 92)Reverse Linked List II
- [Algorithm] 234. Palindrome Linked List / Reverse linked list
- leetcode 207. 课程表---拓扑排序篇一
- leetcode || 50、Pow(x, n)
- Leetcode 703. 数据流中的第 K 大元素(终于解决)
- [LeetCode] 16. 最接近的三数之和 ☆☆☆(双指针)
- [LeetCode] 538. 把二叉搜索树转换为累加树 ☆(中序遍历变形)
- [LeetCode] 206. Reverse Linked List ☆(反转链表)
- leetcode - Rotate List
- leetcode dfs Flatten Binary Tree to Linked List
- 【Leetcode刷题Python】74. 搜索二维矩阵
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- Java Stream 处理分组后取每组最大&Stream流之list转map、分组取每组第一条&Java 8 Collectors:reducing 示例(List分组取最值)