给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
```
题解:golang
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedListToBST(head *ListNode) *TreeNode {
\tif head == nil {
\t\treturn nil
\t}
\tlenList := 0
\tcur := head
\tfor cur != nil {
\t\tcur = cur.Next
\t\tlenList++
\t}
\treturn binarySearch(&head, 0, lenList-1)
}
func binarySearch(head **ListNode, start int, end int) *TreeNode {
\tif start > end {
\t\treturn nil //
\t}
\tmid := (start + end) / 2
\tleft := binarySearch(head, start, mid-1)
\troot := &TreeNode{(*head).Val, nil, nil}
\troot.Left = left
\t*head = (*head).Next
\t//order must leftSubTree, head ,rightSubTree
\tright := binarySearch(head, mid+1, end)
\troot.Right = right
\treturn root
}
```
复杂度分析
- 时间复杂度:
时间复杂度仍然为 O(N)
因为我们需要遍历链表中所有的顶点一次并构造相应的二叉搜索树节点。
- 空间复杂度:
O(logN)
可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制
LeetCode题解黑白圆盘一个圆盘被涂上了黑白二色,两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解:可以用一个相机即可
LeetCode题解圆上任取三点构成锐角三角形的概率来自字节跳动的一道几何题题解:1/4
LeetCode题解深度优先遍历和回溯的关系?深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈