# LeetCode109：有序列表转二叉搜索树

## 题目描述

https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

## 样例

```      0
/ \
-3   9
/   /
-10  5
```

## 解题思路及代码

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
# 采用递归的方式进行求解，由于是已经排序好的单链表，首先获取全部的排序元素值，然后根据取中间元素构建根节点，依次进行递归迭代左右结点即可
def helper(vals):
if vals:
mid = len(vals) // 2
root = TreeNode(vals[mid])
root.left = helper(vals[:mid])
root.right = helper(vals[mid+1:])
return root
return
# 获取所有的元素值
vals = []
return helper(vals)
```

Python版本

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

# pre指针用来将左边从中间结点断开
prev = None

# 迭代执行直到尾指针到达链表结尾
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next

# 从中间结点进行断开
if prev:
prev.next = None

return slow

"""
:rtype: TreeNode
"""

# 如果头结点不存在，直接返回空
return None

# 找到中间结点

# 将中间结点构建成根结点
node = TreeNode(mid.val)

# 如果只有一个元素，则直接返回
return node

# 递归迭代执行，构建左右子树
node.right = self.sortedListToBST(mid.next)
return node
```

Java版本

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
return null;
TreeNode node = new TreeNode(mid.val);
return node;
node.right = this.sortedListToBST(mid.next);
return node;
}
public ListNode findMiddle(ListNode node){
if(node == null)
return null;
ListNode pre = null;
ListNode slow = node;
ListNode fast = node;
while(fast != null && fast.next != null){
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
if(pre != null)
pre.next = null;
return slow;
}
}
```

0 条评论

• ### 【一分钟知识】七种损失函数

0-1, Hinge, Logistic, Cross Entropy, Square, Absolute, Huber

• ### 基于图卷积的价格感知推荐

Paper：Price-aware Recommendation with Graph Convolutional Networks

• ### SIGIR2020 | 基于GCN的鲁棒推荐系统研究

近年来，推荐系统已成为所有电子商务平台中必不可少的组件。然而，推荐系统的评分数据通常来自开放平台，而开放平台可能会存在一群恶意用户故意插入虚假反馈，以使推荐系统...

• ### Leetcode 86. Partition List

版权声明：博客文章都是作者辛苦整理的，转载请注明出处，谢谢！ https://blog.csdn....

• ### Python 中 os.path 模块的

https://docs.python.org/3/library/os.path.html

• ### 漏洞预警：CVE-2019-11043/PHP-FPM(RCE)

2019年9月26日，PHP官方发布漏洞通告称nginx + php-fpm服务器在部分错误配置下存在远程代码执行漏洞。2019年10月22日，外籍白帽子And...

• ### Failed to connect to raw.githubusercontent.com port 443 解决方案

由于某些你懂的因素，导致GitHub的raw.githubusercontent.com域名解析被污染了。

• ### 【NPM库】- 0x05 - 文件、路径操作

1.3. path.dirname、path.join、path.resolve、path.relative

• ### 护网杯easy laravel ——Web菜鸡的详细复盘学习

复现让我发现了很多读wp以为懂了动手做的时候却想不通的漏掉的知识点(还是太菜orz)，也让我对这道题解题逻辑更加理解。所以不要怂，就是干23333！