当前位置： 面试刷题>> 有序链表转换为二分查找树 (经典算法题500道)
### 题目描述
给定一个按升序排列的链表，要求将其转换成一个高度平衡的二分查找树（BST）。高度平衡的二分查找树是指一个二叉树，其中每个节点的两个子树的高度差的绝对值不超过1，并且左子树的所有节点的值均小于其根节点的值，右子树的所有节点的值均大于其根节点的值。
### 示例
假设链表中的元素为 `[1, 2, 3, 4, 5, 6, 7]`，则一个可能的转换后的二分查找树为：
```
4
/ \
2 6
/ \ / \
1 3 5 7
```
### 解题思路
1. **找到链表的中间节点**：使用快慢指针法找到链表的中间节点，这个节点将作为二分查找树的根节点。
2. **递归构建左子树和右子树**：将链表从中间节点断开，分别递归地构建左子树和右子树。左子树包含中间节点之前的所有节点，右子树包含中间节点之后的所有节点。
3. **返回根节点**：将构建好的左子树和右子树连接到中间节点上，并返回中间节点作为根节点。
### PHP 代码示例
```php
class ListNode {
public $val;
public $next;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function sortedListToBST($head) {
if ($head === null) {
return null;
}
if ($head->next === null) {
return new TreeNode($head->val);
}
// 使用快慢指针找到中间节点
$slow = $head;
$fast = $head;
$prevPtr = null;
while ($fast !== null && $fast->next !== null) {
$prevPtr = $slow;
$slow = $slow->next;
$fast = $fast->next->next;
}
// 将链表从中间断开
if ($prevPtr !== null) {
$prevPtr->next = null;
}
// 递归构建左右子树
$root = new TreeNode($slow->val);
$root->left = sortedListToBST($head);
$root->right = sortedListToBST($slow->next);
return $root;
}
```
### Python 代码示例
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sortedListToBST(head):
if not head:
return None
if not head.next:
return TreeNode(head.val)
# 使用快慢指针找到中间节点
slow, fast = head, head
prev_ptr = None
while fast and fast.next:
prev_ptr = slow
slow = slow.next
fast = fast.next.next
# 将链表从中间断开
if prev_ptr:
prev_ptr.next = None
# 递归构建左右子树
root = TreeNode(slow.val)
root.left = sortedListToBST(head)
root.right = sortedListToBST(slow.next)
return root
```
### JavaScript 代码示例
```javascript
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function sortedListToBST(head) {
if (!head) return null;
if (!head.next) return new TreeNode(head.val);
// 使用快慢指针找到中间节点
let slow = head, fast = head, prevPtr = null;
while (fast && fast.next) {
prevPtr = slow;
slow = slow.next;
fast = fast.next.next;
}
// 将链表从中间断开
if (prevPtr) prevPtr.next = null;
// 递归构建左右子树
const root = new TreeNode(slow.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(slow.next);
return root;
}
```
码小课网站中有更多关于算法和数据结构的相关内容分享给大家学习，希望这些示例和解释能帮助你更好地理解和解答这道题。