给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 先用快慢指针找到中间节点
- 分治构建平衡二叉树
- 时间复杂度：$O(NlogN)$，N 为链表长度。
- 空间复杂度：$O(logN)$，N 为链表长度。
JavaScript Code
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {ListNode} head
* @return {TreeNode}
*/
var sortedListToBST = function (head, tail = null) {
if (!head || head === tail) return null;
let slow = head,
fast = head;
while (fast !== tail && fast.next !== tail) {
slow = slow.next;
fast = fast.next.next;
}
const root = new TreeNode(slow.val);
root.left = sortedListToBST(head, slow);
root.right = sortedListToBST(slow.next, tail);
return root;
};C++ Code
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if (head == nullptr) return nullptr;
return sortedListToBST(head, nullptr);
}
TreeNode* sortedListToBST(ListNode* head, ListNode* tail) {
if (head == tail) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (fast != tail && fast->next != tail) {
slow = slow->next;
fast = fast->next->next;
}
TreeNode* root = new TreeNode(slow->val);
root->left = sortedListToBST(head, slow);
root->right = sortedListToBST(slow->next, tail);
return root;
}
};Python Code
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
if not head: return None
prev, slow, fast = None, head, head
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
root = TreeNode(slow.val)
if slow == fast: return root
if prev: prev.next = None
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(slow.next)
return root由于寻找链表中点的时间复杂度是
- 时间复杂度：$O(N)$，N 为链表长度。
- 空间复杂度：$O(N)$，N 为链表长度。
JavaScript Code
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {ListNode} head
* @return {TreeNode}
*/
var sortedListToBST = function (head) {
if (!head) return null;
const nodes = [];
while (head) {
nodes.push(head.val);
head = head.next;
}
return sortedArrayToBST(nodes, 0, nodes.length);
// ********************************************
function sortedArrayToBST(array, start, end) {
if (start >= end) return null;
const mid = (((end - start) >> 1) >> 0) + start;
const root = new TreeNode(array[mid]);
root.left = sortedArrayToBST(array, start, mid);
root.right = sortedArrayToBST(array, mid + 1, end);
return root;
}
};C++ Code
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
vector<int> nodes;
while (head != nullptr) {
nodes.push_back(head->val);
head = head->next;
}
return sortedListToBST(nodes, 0, nodes.size());
}
TreeNode* sortedListToBST(vector<int>& nodes, int start, int end) {
if (start >= end) return nullptr;
int mid = (end - start) / 2 + start;
TreeNode* root = new TreeNode(nodes[mid]);
root->left = sortedListToBST(nodes, start, mid);
root->right = sortedListToBST(nodes, mid + 1, end);
return root;
}
};