本文最后更新于 2025-03-31T00:09:09+08:00
题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表: [-10, -3, 0, 5, 9],
一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:
0 / \ -3 9 / / -10 5
|
题目思路
- 1、本题相当于将链表转化为一个二叉搜索树(Binary Search Tree : BST)
- 2、基于中序遍历恢复二叉搜索树,即可从任意节点出发,以节点左边的升序序列作为左子树,右边升序序列为右子树,即可得到二叉搜索树,本题要建立一个高度平衡的二叉搜索树,那么左右高度差至多为 1,故从链表的中点开始建立二叉搜索树最好。
- 3、本题也可以用 BFS 建树,DFS 填节点值,但这样空间复杂度较高,时间复杂度跟递归链表差不多的情况下,确实不是特别优秀的解法,不过也可以用来熟悉一下 DFS 与 BFS。
代码块。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
|
class Solution { public: TreeNode* sortedListToBST(ListNode* head) { if(head == nullptr) return nullptr; if(head -> next == nullptr) { TreeNode* root = new TreeNode(head -> val); return root; } ListNode* fast = head; int len = 1; while(fast -> next != nullptr) { fast = fast -> next; len++; } len = len >> 1; ListNode* slow = head; ListNode* p = slow; while(len--) { p = slow; slow = slow -> next; } p -> next = nullptr; TreeNode* root = new TreeNode(slow -> val); root -> left = sortedListToBST(head); root -> right = sortedListToBST(slow -> next); return root; } };
|
复杂度
时间复杂度:O(log n)
空间复杂度:O(1)
Day-09 109. 有序链表转换二叉搜索树
https://chaggle.github.io/2021/09/18/Leetcode/91-day/day-09/