将链表转成数组
解题思路
BST 的中序遍历是升序的，等同于根据中序遍历的序列恢复二叉搜索树；
将链表转成升序的数组，可以让 升序序列 的 中间元素 作为根节点（高度平衡），不断递归左子树和右子树；
这样得到的树就是一棵二叉搜索树；
复杂度
-
时间复杂度：
O(nlogn)，其中 n 是链表的长度； -
空间复杂度：
O(logn)，这里只计算除了返回答案之外的空间，平衡二叉树的高度为O(logn)，即为递归过程中栈的最大深度，也就是需要的空间；
代码实现
var sortedListToBST = function (head) {
// 1. 将链表转成数组
const list = [];
while (head) {
list.push(head.val);
head = head.next;
}
// 2. 利用 「将有序数组转换为二叉搜索树」
const dfs = function (nums) {
if (nums.length === 0) return null;
// 以升序数组的中间元素作为根节点 root
const mid = nums.length >> 1;
const root = new TreeNode(nums[mid]);
root.left = dfs(nums.slice(0, mid));
root.right = dfs(nums.slice(mid + 1));
return root;
};
return dfs(list);
};
中序遍历 + 链表中点（推荐）
解题思路
BST 的中序遍历是升序的，等同于根据中序遍历的序列恢复二叉搜索树；
利用快慢指针寻找链表的中点，将该中点作为 BST 的根节点，
- 利用链表的前半部分递归构建左子树；
- 利用链表的后半部分递归构建右子树；
不断递归左子树和右子树，这样得到的树就是一棵二叉搜索树；
复杂度
-
时间复杂度：
O(nlogn)，其中 n 是链表的长度； -
空间复杂度：
O(logn)，这里只计算除了返回答案之外的空间，平衡二叉树的高度为O(logn)，即为递归过程中栈的最大深度，也就是需要的空间；
代码实现
var sortedListToBST = function (head) {
const dfs = (head, tail) => {
if (head === tail) return null;
// 1. 利用快慢指针找到中间的元素作为根节点
let slow = fast = head;
while (fast !== tail && fast.next !== tail) {
slow = slow.next;
fast = fast.next.next;
}
// 2. 中间元素 slow 作为根节点
let root = new TreeNode(slow.val);
root.left = dfs(head, slow);
root.right = dfs(slow.next, tail);
return root;
}
return dfs(head, null)
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 84. 柱状图中最大的矩形
上一篇
评论
