Leetcode: 【每日一题】- 2019-08-28 - 109. 有序链表转换二叉搜索树-推荐

[watchpoints]

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[watchpoints]

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 {
    if head == nil {
        return nil
    }
    lenList := 0
    cur := head

    for cur != nil {
        cur = cur.Next
        lenList++
    }

    return binarySearch(&head, 0, lenList-1)

}

func binarySearch(head **ListNode, start int, end int) *TreeNode {
    if start > end {
        return nil //
    }

    mid := (start + end) / 2
    left := binarySearch(head, start, mid-1)
    root := &TreeNode{(*head).Val, nil, nil}
    root.Left = left
    *head = (*head).Next

    //order must leftSubTree, head ,rightSubTree
    right := binarySearch(head, mid+1, end)
    root.Right = right

    return root
}

复杂度分析

• 时间复杂度：
  时间复杂度仍然为 O(N)
  因为我们需要遍历链表中所有的顶点一次并构造相应的二叉搜索树节点。

• 空间复杂度：
  O(logN)

[raof01]

static TreeNode* bstFromSortedList(ListNode*& head, int start, int end) {
    if (start > end) return nullptr;
    auto mid = start + (end - start) / 2;
    auto left = bstFromSortedList(head, start, mid - 1);
    if (head == nullptr) return nullptr;
    auto root = new TreeNode(head->val);
    head = head->next;
    root->left = left;
    root->right = bstFromSortedList(head, mid + 1, end);
    return root;
}

static TreeNode* bstFromSortedList(ListNode* head) {
    auto len = 0;
    auto p = head;
    while (p != nullptr) {
        ++len;
        p = p->next;
    }
    return bstFromSortedList(head, 1, len);
}

[xiongcaihu]

``` .js
// 将数组从中间分割，左边集合用来构建左子树，中间的点为根节点
var sortedListToBST = function(head) {
if (head == null || head.val == null) return null;
var arry = [];
while (head) {
if (head.val != null) {
arry.push(head.val);
}
head = head.next;
}
if (arry == null || arry.length == 0) return null;

return temp(0, arry.length - 1);

function temp(start, end) {
    var node = new TreeNode();
    if (end - start == 0) {
        return new TreeNode(arry[end]);
    }
    if (end - start == 1) {
        node.val = arry[end];
        node.left = new TreeNode(arry[start]);
        return node;
    }
    var middleIndex = parseInt((end - start) / 2) + start;
    node.val = arry[middleIndex];

    node.left = temp(start, middleIndex - 1);
    node.right = temp(middleIndex + 1, end);
    return node;
}

};
```

>

[wjj31767]

python3

# 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:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        tmp = []
        while head:
            tmp.append(head.val)
            head = head.next
        def dfs(tmp):
            if len(tmp) == 0:
                return None
            if len(tmp) == 1:
                return TreeNode(tmp[0])
            ii = int(len(tmp) / 2)
            root = TreeNode(tmp[ii])
            root.left = dfs(tmp[ : ii])
            root.right = dfs(tmp[ii + 1 :])
            return root
        return dfs(tmp)

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.