有序链表转换二叉搜索树
- ① 有序链表转成有序数组
- ② 根据有序数组构建平衡二叉树
注意:能够转换成
平衡二叉树
var sortedListToBST = function (head) {
// ① 有序链表转成有序数组
let nums = [];
let p = head;
while (p) {
nums.push(p.val);
p = p.next;
}
// ② 根据有序数组构建平衡二叉树
let n = nums.length;
return build(0, n - 1);
function build(left, right) {
if (left > right) return null;
let mid = Math.floor((left + right) / 2);
let root = new TreeNode(nums[mid]);
// 递归构建左子树
root.left = build(left, mid - 1);
// 递归构造右子树
root.right = build(mid + 1, right);
return root;
}
};