【Day 9 】2021-09-18 - 109. 有序链表转换二叉搜索树

[azl397985856]

109. 有序链表转换二叉搜索树

入选理由

暂无

题目地址

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

前置知识

• 递归
• 二叉搜索树的任意一个节点，当前节点的值必然大于所有左子树节点的值。同理,当前节点的值必然小于所有右子树节点的值

  题目描述

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

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

  0
 / \

-3 9 / / -10 5

[yanglr]

思路

先遍历完链表, 再用dfs构建bst

代码

实现语言: C++

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> nums;
        getNums(head, nums);
        return dfs(nums, 0, nums.size() - 1);
    }
    void getNums(ListNode* head, vector<int>& nums)
    {
        while (head)
        {
            nums.push_back(head->val);
            head = head->next;
        }
    }
    TreeNode* dfs(vector<int>& nums, int start, int end)
    {
        if (start == end)
        {
            TreeNode* root = new TreeNode(nums[start]);
            return root;
        }
        if (start < end)
        {
            int m = (end - start) / 2 + start;
            auto leftChild =  dfs(nums, start, m - 1);
            auto rightChild =  dfs(nums, m + 1, end);
            TreeNode* root = new TreeNode(nums[m], leftChild, rightChild);
            return root;
        }
        return nullptr;
    }
};

代码已上传到: leetcode-ac/91algo daily - github.com

复杂度分析

• 时间复杂度：O(n log n)
• 空间复杂度：O(n), 用了个额外的数组存储链表结点的值

[RocJeMaintiendrai]

思路

使用快慢指针找到list的中点，中点作为当前的root，然后对左右进行递归调用。

代码

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        return toBST(head, null);
    }

    private TreeNode toBST(ListNode head, ListNode tail) {
        if(head == tail) return null;
        // find the middle node
        ListNode slow = head, fast = head;
        while(fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = toBST(head, slow);
        root.right = toBST(slow.next, tail);
        return root;
    }
}

复杂度分析

时间复杂度

所有数据遍历一遍，O(n)

空间复杂度

O(n)

[yachtcoder]

1. Find the median node of the list with fast & slow pointers.
2. Break the list into three parts: left, median, and right
3. Use the median node as root, build two sub BST recursively on left and right.

Time: O(n) Space: O(lg(n)) due to the recursion stack

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        def build(head):
            if not head: return None
            if not head.next: return TreeNode(val = head.val)
            pre, fast, slow = head, head, head
            while fast and fast.next:
                fast = fast.next.next
                pre = slow
                slow = slow.next
            pre.next = None #median: slow, right: slow.next
            return TreeNode(val = slow.val, left = build(head), right = build(slow.next))
        return build(head)

[JiangyanLiNEU]

Idea

Use divide and conquer to build tree:

• find the middle node in the linked list
• break the connection from the previous node and next node, so here we got three linked list
  • 10 --> -3 --> 0 --> 5 --> 9
  • br br
• the first and third segments do the same thing repeadly until no node left, tree node is the middle node

Implement ( Runtime = O( n ), Space=( n ) )

class Solution(object):
    def sortedListToBST(self, head):
        # Edge cases to stop recursion
        if not head:
            return None
        if not head.next:
            # print('get node, ', pointer.val)
            return TreeNode(head.val)
        # Find the length of this linkedlist
        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next
        # Break it into three segments: 
        middle = length//2
        dummy = ListNode(0,head)
        pre = dummy
        pointer = pre.next
        while middle>0:
            pre = pointer
            pointer = pointer.next
            middle -= 1
        # Break the connection
        pre.next = None
        right = pointer.next
        pointer.next = None
        left = dummy.next
        # Do recursion
        return TreeNode(pointer.val, self.sortedListToBST(left), self.sortedListToBST(right))

[ivalkshfoeif]

class Solution {
    ListNode i;
    public TreeNode sortedListToBST(ListNode head) {
        int length = 0;
        ListNode p = head;
        i = head;
        while (p != null){
            length++;
            p = p.next;
        }

        return buildTree(0, length - 1);

    }
    private TreeNode buildTree(int lo, int hi){
        if (lo > hi){
            return null;
        }
        TreeNode node = new TreeNode();
        int mid = lo + (hi - lo)/2;
        node.left = buildTree(lo,mid - 1);
        node.val = i.val;
        i = i.next;
        node.right = buildTree(mid+1,hi);
        return node;
    }

}

O(N) O(logN) 通过数组长度预设一个Tree, 然后中序遍历赋值 也可以把List转换成数组，然后中序遍历

[Jding0]

思路

create dumpy head and exchange two neighors node

代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummyHead = ListNode(0)
        dummyHead.next = head
        temp = dummyHead
        while temp.next and temp.next.next:
            node1 = temp.next
            node2 = temp.next.next
            temp.next = node2
            node1.next = node2.next
            node2.next = node1
            temp = node1
        return dummyHead.next

复杂度

时间复杂度：O(n)，其中 nn 是链表的节点数量。需要对每个节点进行更新指针的操作。 空间复杂度：O(1)。

[ai2095]

LC109. Convert Sorted List to Binary Search Tree

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

Topics

• Linked List
• Array
• BST

Similar Questions

Medium

• https://leetcode.com/problems/design-add-and-search-words-data-structure/
• https://leetcode.com/problems/design-search-autocomplete-system/
• https://leetcode.com/problems/replace-words/
• https://leetcode.com/problems/implement-magic-dictionary/

思路

Convert the linked list to list. Use recursion to build the tree in preorder.

代码 Python

# 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: Optional[ListNode]) -> Optional[TreeNode]:
        # Border check
        if not head:
            return None
        if head and head.next == None:
            return TreeNode(head.val)

        # convert Linkedlist to list
        lst = []
        cur = head
        while cur:
            lst.append(cur.val)
            cur = cur.next

        # Recursion
        def recur(node_list):
            if len(node_list) == 0:
                return
            cur_node = TreeNode(val=node_list[len(node_list)//2])
            left = recur(node_list[:len(node_list)//2])
            if left:
                cur_node.left = left
            right = recur(node_list[len(node_list)//2 + 1:])
            if right:
                cur_node.right = right

            return cur_node

        return recur(lst)

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

[BpointA]

思路

快慢指针找中点，再从中点做左右切割，利用递归得到树。递归出的条件：链表没有节点。

Python3代码

# 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:
        if head==None:
            return head
        if head.next==None:
            return TreeNode(head.val)
        slow=head
        fast=head
        pre=None
        while fast!=None and fast.next!=None:
            fast=fast.next.next
            pre=slow
            slow=slow.next
        pre.next=None
        left=self.sortedListToBST(head)
        right=self.sortedListToBST(slow.next)
        t=TreeNode(slow.val)
        t.left=left
        t.right=right
        return t

复杂度

时间复杂度：O(nlogn)
空间复杂度：O(logn) （logn为构造二叉树需要的空间）

[fzzfgbw]

思路

遍历节点值，再递归

代码

func sortedListToBST(head *ListNode) *TreeNode {
    if head == nil {
        return nil
    }
    var s []int
    for head != nil {
        s = append(s, head.Val)
        head = head.Next
    }
    return dfs(s)
}
func dfs(s []int) *TreeNode {
    if len(s) > 0 {
        return &TreeNode{s[len(s)/2], dfs(s[:len(s)/2]), dfs(s[len(s)/2+1:])}
    } else {
        return nil
    }
}

复杂度分析

• 时间复杂度：O(N)。
• 空间复杂度：O(N)。

[leungogogo]

LC109. Convert Sorted List to Binary Search Tree

Method 1. Divide and Conquer

Main Idea

If we pick a node as root of the tree, then we will need to determine the left and right subtrees with the list nodes on the left and right hand sides, which is the same problem but with a smaller size.

Also, we want the BST to be balanced, so when constructing the tree, we want to choose the middle list node as the root, so left and right will have same number of nodes, or one side will have an extra node.

Algorithm

1. Base case: If there is only one node left, return it as a new TreeNode.
2. Get the middle node.
3. Recusrivly call the function on the left and right lists and get the left and right subtree.

Code

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);

        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode prev = head;
        while (prev.next != slow) {
            prev = prev.next;
        }
        prev.next = null;
        TreeNode left = sortedListToBST(head);
        TreeNode right = sortedListToBST(slow.next);
        TreeNode root = new TreeNode(slow.val);
        root.left = left;
        root.right = right;
        return root;
    }
}

Complexity Analysis

Time: O(nlogn), divide and conquer.

Space: O(height) = O(logn) for recursive calls.

Tradeoff

Notice we can convert the linked list to an array list so we have random access to the middle node, which makes the time compleixty O(n) since we no longer have to traverse the entire list each layer. But the space complexity will be O(n) to store the array.

Method 2. In-Order Traversal

Main Idea

The bottleneck of method 1 is that we have to either find the mid node each recursive call or convert the linked list to array list, which either costs time or space. But can we do better?

First recall the fact that a sorted list/array is the in-order traversal of a bst. Which means we can traverse the list once, and build the tree, like how we did in-order traversal, the left subtree is traversed and built first, then we create the root node, finally the right subtree.

We can use a global variable cur to represent the current node we are processing. Since we are doing an in-order traversal, all the nodes will be created in order, e.g, node i won't be created until all nodes 0:i-1 are cteated.

Algorithm

1. Define inOrder(int i, int j) to be the problem of the converting list[i:j] to BST.
2. Base case: if i > j, return null.
3. Calculate mid = i + (j - i) / 2, left subtree will be inOrder(i, mid - 1), and then we create our root with the current node cur, then the next node to create will be cur.next, and we build the right sutree with inOrder(mid + 1, j).

Code

class Solution {
    private ListNode cur;
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        cur = head;
        int n = getLength(head);
        return inOrder(0, n - 1);
    }

    private TreeNode inOrder(int l, int r) {
        if (l > r) return null;
        int m = l + (r - l) / 2;
        TreeNode left = inOrder(l, m - 1);
        TreeNode root = new TreeNode(cur.val);
        cur = cur.next;
        TreeNode right = inOrder(m + 1, r);
        root.left = left;
        root.right = right;
        return root;
    }

    private int getLength(ListNode head) {
        int cnt = 0;
        while (head != null) {
            head = head.next;
            ++cnt;
        }
        return cnt;
    }
}

Complexity Analysis

Time: O(n)

Space: O(logn) for recursive calls.

[xitice]

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {

  if (!head) return null;
  const nums = [];

  while(head) {
    nums.push(head.val);
    head = head.next;
  }
  return dfs(nums, 0, nums.length - 1);

  function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
  }

  function dfs(arr, low, high) {
    if (low > high) return null;
    let mid = Math.floor((low + high) / 2);
    let node = new TreeNode(arr[mid]);

    node.left = dfs(arr, low, mid - 1);
    node.right = dfs(arr, mid + 1, high);

    return node;
  }
};

[zjsuper]

Idea: fast and slow pointers find root point, then recursion Time: O(nlogn), Space:(logn)

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return head
        prev = None
        slow = head
        fast = head
        while fast and fast.next:
            fast = fast.next.next
            prev = slow
            slow = slow.next

        if prev:
            prev.next = None
        node = TreeNode(slow.val)
        if slow == fast:
            return node
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(slow.next)
        return node

[nonevsnull]

思路

• 拿到题的直觉解法

链表的中点是树的root，左半是左子树的全部节点，右半是右子树的全部节点；

链表的中点可以通过快慢指针找到；

可以用递归(pre-order dfs)来生成树，递归的结构

• params: head of listnode
• return：root of tree
• 递归终止条件：head of listnode is null

注意：影响bug free的问题

• 注意左子树。使用了dummy后，设置leftHead的时候要使用dummy.next而不是直接使用head，因为要考虑到当前head只有一个node，它的左右分枝因此都为null，如果直接使用head，会导致多出来了分枝。dummy.next可以很智能的规避这个问题。
• 可以用dummy做pre，返回dummy.next很方便；

AC

• 官网有意思的解法

BST的in-order顺序和linkedlist顺序是一致的，既然如此，我们就可以匹配这两者。但题目是生成树，因此在没有树的时候，我们如何来in-order dfs？ 这个解法巧妙的模拟了in-order，即便没有树，也可以dfs，只要保持相对同步就行。使用的工具是左右子树在linkedlist的index。

AC

代码

//pre-order dfs recursion
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            TreeNode root = new TreeNode(head.val);
            return root;
        }

        return helper(head);

    }

    public TreeNode helper(ListNode head){
        if(head == null) return null;
        //find mid node in the listnodes
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode fast = dummy;
        ListNode slow = dummy;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //slow.next is root, then slow should point to null
        ListNode rootNode = slow.next;
        TreeNode root = new TreeNode(rootNode.val);
        slow.next = null;
        ListNode leftHead = dummy.next;
        ListNode rightHead = rootNode.next;
        root.left = helper(leftHead);
        root.right = helper(rightHead);

        return root;
    }
}

//边模拟in-order, 边生成
class Solution {
    ListNode head;
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        if(head.next == null) {
            TreeNode root = new TreeNode(head.val);
            return root;
        }

        this.head = head;
        int length = 0;
        ListNode cur = head;
        while(cur != null){
            length++;
            cur = cur.next;
        }

        return inorder(0, length);
    }

    public TreeNode inorder(int left, int right){
        if(left > right || head == null) return null;
        int mid = left + (right - left) / 2;
        TreeNode l = inorder(left, mid - 1);

        TreeNode root = new TreeNode(head.val);
        head = head.next;

        root.left = l;
        root.right = inorder(mid + 1, right);

        return root;
    }
}

复杂度

pre-order dfs time: O(NlogN), 递归的部分会有logN次，每次会有快慢指针N/2次，因此总量N * longN space: O(logN),主要是递归用来存储栈的占用。

simulate in-order time: O(N)，递归的复杂度只有logN，但我们要通过一次遍历链表查询长度，因此复杂度最高为N space: O(logN)，主要是递归存储栈的占用。

[yiwchen]

思路： 暴力做……

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        l = 0 
        cur = head
        while cur:
            cur = cur.next
            l += 1

        def toTree(left, right):
            nonlocal head

            if left > right: 
                return None

            mid = (left+ right) // 2

            left = toTree(left, mid - 1)

            t = TreeNode(head.val)

            head = head.next
            right = toTree(mid + 1, right)

            t.left = left

            t.right = right

            return t

        tree = toTree(0, l - 1)
        return tree

TC: O(N) 要找一次长度

SC: O(Log(N)) 主要是call stack

[erik7777777]

思路

Recursively find the mid point of the list, and break the list into two parts, use the smaller part as left node and the larger part as the right node according to the definition of the BST.

代码

public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        ListNode prev = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        ListNode right = slow.next;
        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(right);
        return root;
    }

复杂度

time : O(nlogn) n(elements in every layer) * logn(number of layers). space : O(height of stack/tree) -> O(logn)

idea

use a list to store all the element in the linked list : cost O(n) time use list.get(i) to retrieve the element in the middle of the list : cost O(1)

in this way our time complexity will be around O(n) and space complexity will be around O(n)

[cicihou]

# 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:
        if not head:
            return
        if not head.next:
            return TreeNode(head.val)

        fast = slow = head
        pre = None
        while fast and fast.next:
            pre = slow
            fast = fast.next.next
            slow = slow.next
        root = TreeNode(slow.val)
        pre.next = None
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

[falconruo]

思路: 方法一、递归 因为是升序递增的linked list, 使用快慢指针的方法每次取中间结点创建树的root结点,利用递归思路再分别处理左右子树(head -> slow, slow->next -> tail)

方法二、模拟中序遍历

1. 先遍历链表一遍计算出总的结点数len, 用两个指针l = 0, r = len
2. 递归：
   • 每次取中间结点作为root = l + (r - l)/2
   • 先处理左子树(左半部分链表)
   • 生成根结点(head->val)
   • 移动head一步
   • 再处理右子树

复杂度分析: 方法一、

1. 时间复杂度: O(nlogn), n为给定链表长度， 递归的部分会有logN次，每次会有快慢指针N/2次，因此总量N * longN
2. 空间复杂度: O(logn), 递归栈，主要是递归用来存储栈的占用

方法二、

1. 时间复杂度: O(n), n为给定链表长度， 递归的复杂度只有logN，但我们要通过一次遍历链表查询长度，因此复杂度最高为N
2. 空间复杂度: O(logn), 递归栈， 主要是递归用来存储栈的占用

代码(C++):

方法一、递归
/**
 * 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) return nullptr;
        if (!head->next) {
            TreeNode* node = new TreeNode(head->val);
            return node;
        }

        ListNode* prev = nullptr;
        ListNode* fast = head;
        ListNode* slow = head;

        // find the mid node of linked list
        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }

        // break the linked list
        prev->next = nullptr;

        TreeNode* root = new TreeNode(slow->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);

        return root;
    }
};

方法二、
/**
 * 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:
    ListNode* head;
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) {
            TreeNode* node = new TreeNode(head->val);
            return node;
        }

        cur = head;
        int len = 0;
        while (cur) {
            ++len;
            cur = cur->next;
        }

        cur = head;
        return buildTree(0, len);
    }
private:
    ListNode* cur;

    TreeNode* buildTree(int l, int r) {
        if (l > r || !cur) return nullptr;

        int m = l + (r - l)/2;
        TreeNode* lf = buildTree(l, m - 1);

        TreeNode* root = new TreeNode(cur->val);
        cur = cur->next;
        root->left = lf;
        root->right = buildTree(m + 1, r);

        return root;
    }
};

[xj-yan]

/**
 * Definition for singly-linked list.
 * 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 {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        List<Integer> list = convertNodeToList(head);
        return buildBST(list, 0, list.size() - 1);
    }

    private List<Integer> convertNodeToList(ListNode head){
        ListNode curt = head;
        List<Integer> list = new ArrayList<>();
        while (curt != null){
            list.add(curt.val);
            curt = curt.next;
        }
        return list;
    }

    private TreeNode buildBST(List<Integer> list, int left, int right){
        if (left > right) return null;
        if (left == right) return new TreeNode(list.get(left));

        int mid = (right - left) / 2 + left;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = buildBST(list, left, mid - 1);
        root.right = buildBST(list, mid + 1, right);
        return root;
    }
}

Time Complexity: O(n) Space Complexity: O(n)

[wangzehan123]

题目地址(109. 有序链表转换二叉搜索树)

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

题目描述

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

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

/**
 * Definition for singly-linked list.
 * 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 {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        else if(head.next == null) return new TreeNode(head.val);
        ListNode pre = head;
        ListNode p = pre.next;
        ListNode q = p.next;
        //找到链表的中点p
        while(q!=null && q.next!=null){
            pre = pre.next;
            p = pre.next;
            q = q.next.next;
        }
        //将中点左边的链表分开
        pre.next = null;
        TreeNode root = new TreeNode(p.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(p.next);
        return root;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[pophy]

思路

• 利用快慢指针 找到链表 Mid - 1的位置
• mid-1的下一个 就是二叉树的头
• 断开mid -1和mid的连接
• 递归分别生成left 和 right
  • 左边的头是head 右边的头是mid + 1
  • 递归退出条件是 head == null 或者head.next == null

Java Code

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }

        ListNode preMid = findMid(head);
        TreeNode root = new TreeNode(preMid.next.val);
        ListNode nextMid = preMid.next.next;
        preMid.next = null;
        TreeNode left = sortedListToBST(head);
        TreeNode right = sortedListToBST(nextMid);
        root.left = left;
        root.right = right;
        return root;
    }

    private ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        if (fast != null && fast.next != null) {
            fast = fast.next.next;
        }
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

时间&空间

• 时间 O(n*log(n))
• 空间 O(1) 不考虑递归栈系统内存

[ruohai0925]

思路

关键点

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:

        def getMedian(left: ListNode, right: ListNode) -> ListNode: # right包含了None的情况
            fast = slow = left # 标准快慢指针的模板
            while fast != right and fast.next != right:
                fast = fast.next.next
                slow = slow.next
            return slow

        def buildTree(left: ListNode, right: ListNode) -> TreeNode:
            if left == right:
                return None
            mid = getMedian(left, right)
            root = TreeNode(mid.val)
            root.left = buildTree(left, mid)
            root.right = buildTree(mid.next, right)
            return root

        return buildTree(head, None)

复杂度分析

时间复杂度：$O(nlogn)$

空间复杂度：$O(logn)$

[pan-qin]

idea: divide and conquer implemented by recursion. find the mid point of the list, which is the root of the tree. recursion on the right side. use a prev pointer to point to the node before mid point, make prev.next=null to make a new list of left side, then recursion on the left side. Time: O(nlogn) Space: O(n) /**

• Definition for singly-linked list.
• 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 { public TreeNode sortedListToBST(ListNode head) { if(head==null) return null; if(head.next==null) { TreeNode root = new TreeNode(head.val); return root; } //find the mid of list ListNode fast=head, slow=head,prev=head; while(fast!= null && fast.next!=null) { fast=fast.next.next; prev=slow; slow=slow.next; } prev.next=null; TreeNode root = new TreeNode(slow.val); root.left=sortedListToBST(head); root.right=sortedListToBST(slow.next); return root;

  } }

[BlueRui]

Problem 109. Convert Sorted List to Binary Search Tree

Algorithm

• Find the middle ListNode and use it as the root.
• Recursively call the sortedListToBST method on the left half and right half, and assign their results as left and right children of the root.

Complexity

• Time Complexity: O(NlogN). At each level of the tree, we need O(N) to find the middle node. There are logN levels.
• Space Complexity: O(logN) which is the height of the tree and the call stack.

Code

Language: Java

public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);

        ListNode mid = findMid(head);
        TreeNode root = new TreeNode(mid.val);
        root.left = sortedListToBST(head);
        root.right =sortedListToBST(mid.next);
        return root;
    }

    private ListNode findMid(ListNode head) {
        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        return slow;
    }

[mmboxmm]

今天不想写题解

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);

        ListNode mid = findMid(head);
        TreeNode res = new TreeNode(mid.val);

        res.left = sortedListToBST(head);
        res.right = sortedListToBST(mid.next);

        return res;
    }

    private ListNode findMid(ListNode head) {
        ListNode slow = head, fast = head, prev = null;

        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        return slow;
    }

[yingliucreates]

link:

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

代码 Javascript

const sortedListToBST = function (head) {
  if (!head) return null;
  const sorted = [];
  let cur = head;

  while (cur) {
    sorted.push(cur.val);
    cur = cur.next;
  }

  const generate = (l, r) => {
    if (l > r) return null;
    const mid = Math.floor((r + l) / 2);
    let val = sorted[mid];
    const node = new TreeNode(val);
    node.left = generate(l, mid - 1);
    node.right = generate(mid + 1, r);
    return node;
  };

  return generate(0, sorted.length - 1);
};

复杂度分析

时间 O(n) 空间 O(n)

[Mahalasu]

思路

Divide and Conquer

# 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 findMiddle(self, head):
        prevPtr = None
        slowPtr = head
        fastPtr = head

        while fastPtr and fastPtr.next:
            prevPtr = slowPtr
            slowPtr = slowPtr.next
            fastPtr = fastPtr.next.next

        if prevPtr:
            prevPtr.next = None

        return slowPtr

    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None

        mid = self.findMiddle(head)
        node = TreeNode(mid.val)

        if head == mid:
            return node

        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(mid.next)
        return node

T: O(nlong) S: O(logn)

[XinnXuu]

思路

通过快慢指针找出链表的中位数，作为当前树的根节点。左右继续递归建立左右子树。

代码

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null){
            TreeNode root = new TreeNode(head.val);
            return root;
        }
        return dfs(head,null);
    }

    private TreeNode dfs(ListNode head, ListNode tail){
        if (head == tail){
            return null;
        }
        ListNode fast = head, slow = head;
        while (fast != tail && fast.next != tail){
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode median = new TreeNode(slow.val);
        median.left = dfs(head, slow);
        median.right = dfs(slow.next, tail);
        return median;
    }
}

复杂度分析

• 时间复杂度：O(NlogN),递归树深度logN,每层基本操作数N
• 空间复杂度：O(1)

[Menglin-l]

思路：

1.用快慢指针找到中间的节点，即BST的根，

2.重复1中操作，按照根-左-右的顺序递归生成树，其中心思想是“先把根节点搞定，再用同样的方法去搞定左子树的根和右子树的根，从而生成一棵树”。

---

代码部分：

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);

        ListNode fast = head;
        ListNode slow = head;
        ListNode preSlow = null;

        while (fast != null && fast.next != null) {
            preSlow = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        TreeNode root = new TreeNode(slow.val);
        preSlow.next = null;

        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);

        return root;

    }
}

---

复杂度：

Time: O(NlogN)

Space: O(logN)，递归栈

[heyqz]

先找到中点作为root，再递归构建树

代码

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None         
        pre, slow, fast = None, head, head

        while fast and fast.next:
            pre, slow, fast = slow, slow.next, fast.next.next

        if pre:
            pre.next = None
        else:
            return TreeNode(head.val)

        root = TreeNode(slow.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)

        return root 

复杂度

time complexity: O(nlogn) space complexity: O(1)

[chen445]

思路

solution1: We convert linked list to an array, and find the middle node as the root. We can recursively calling itself to build BST.

solution2: We can use two pointers to find the middle node as the root. We recursively process left subtree and right subtree.

代码

solution 1:

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        result=[]
        while head:
            result.append(head.val)
            head=head.next
        return self.binary_search_tree(result,0,len(result)-1)
    def binary_search_tree(self,arr,start,end):
        if start > end:
            return None
        middle=start+(end-start)//2
        root=TreeNode(arr[middle])
        root.left=self.binary_search_tree(arr,start,middle-1)
        root.right=self.binary_search_tree(arr,middle+1,end)
        return root

solution2:

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)
        dummy=ListNode(0)
        dummy.next=head
        slow, fast = dummy,head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        root=TreeNode(slow.next.val)
        root.right=self.sortedListToBST(slow.next.next)
        slow.next=None
        root.left =self.sortedListToBST(head)
        return root

复杂度

Solution 1:

• Time: O(n) n is the number of nodes
• Space: O(n)

Solution 2:

• Time: O(nlogN)
• Space: O(logN)

[hwpanda]

const sortedListToBST = (head) => {
    if (!head) return head;
    let hashArr = [];

    let pointer = head;
    while (pointer) {
        hashArr.push(pointer.val);
        pointer = pointer.next;
    }

    // build up the tree recursively
    const helper = (left, right) => {
        if (left > right) return null;

        let index = Math.floor((right + left) / 2);
        let newNode = new TreeNode(hashArr[index]);

        newNode.left = helper(left, index - 1);
        newNode.right = helper(index + 1, right);

        return newNode;
    };

    return helper(0, hashArr.length - 1);
};

[kidexp]

thoughts

每次找中点，左边作为左子树，右边是右子树，递归

code

def find_mid_of_linked_list(head):
    if not head or not head.next:
        return head
    dummy_head = ListNode(0, head)
    slow = fast = dummy_head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    return mid

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        mid = find_mid_of_linked_list(head)
        if mid:
            root = TreeNode(mid.val)
            if head != mid:
                root.left = self.sortedListToBST(head)
            if mid.next:
                root.right = self.sortedListToBST(mid.next)
            return root
        else:
            return None

complexity

time complexity O(nlgn)

space complexity O(1)

[zol013]

取链表中点为root node，左半作为左子树，右半作为右子树，然后递归 Python 3 code:

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head: return None
        if not head.next: return TreeNode(head.val)
        curr = head
        length = 1
        while curr.next:
            curr = curr.next
            length += 1
        mid = (length - 1) // 2
        pt = head
        while mid - 1 > 0:
            pt = pt.next
            mid -= 1
        root_prev = pt
        root = pt.next
        root_after = root.next
        root_prev.next = None
        root_node = TreeNode(root.val)
        root_node.left = self.sortedListToBST(head)
        root_node.right = self.sortedListToBST(root_after)
        return root_node

Time Complexity: O(nlog(n)) : n + n/2 + n/4 + ..... Space Complexity: O(log(n)): because we are truncating n by half everytime we use recursion.

[carsonlin9996]

1. 寻找中点， 将其建立一个node
2. 把中点的前一个点断开， 递归第一步

class Solution { public TreeNode sortedListToBST(ListNode head) {

    if (head == null) {
        return null;
    }

    if (head.next == null) {
        return new TreeNode(head.val);
    }

    ListNode dis = null;

    ListNode slow = head;
    ListNode fast = head;
    //finds mid point
    while (fast != null && fast.next != null) {
        dis = slow;
        slow = slow.next;
        fast = fast.next.next;
    }

    dis.next = null;

    TreeNode root = new TreeNode(slow.val);

    root.left = sortedListToBST(head);
    root.right = sortedListToBST(slow.next);

    return root;

}

}

[chenming-cao]

解题思路

递归，每次找到链表中点，建立TreeNode，中点左右分割得两个链表，然后继续找中点，建立TreeNode，分割链表。。。找中点最初想法是遍历链表求长度，然后算出中点位置，继续遍历找到中点，结果超时。后改为快慢指针找中点，只需要一次遍历。

代码

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);

        ListNode root;
        ListNode left = head;
        ListNode pre = null;
        ListNode right = null;

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        root = slow;
        right = root != null ? root.next : null;
        pre.next = null;

        return new TreeNode(root.val, sortedListToBST(left), sortedListToBST(right));
    }
}

复杂度分析

令链表长度为N

• 时间复杂度：O(NlogN)，运用递归，递归树深度为logN，每层操作数为N
• 空间复杂度：O(logN)，递归树深度为logN，每个递归函数空间复杂度为O(1)

[Alanwgy]

创建两个快慢指针，找中间节点

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:

        if not head:
            return 
        if not head.next:
            return TreeNode(head.val)
        slow, fast = head, head.next.next
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        tmp = slow.next

        slow.next = None
        root = TreeNode(tmp.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(tmp.next)
        return root

[tongxw]

思路

快慢指针找链表最中间的节点做为树根。然后对左半链表和右半链表进行递归，生成左右子树。

代码

/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
  return recurBuild(head, null);
};

function recurBuild(start, end) {
  if (start === end) {
    return null;
  }
  if (start.next === end) {
    return new TreeNode(start.val);
  }

  let fast = start;
  let slow = start;
  while (fast != end && fast.next !== end) {
    slow = slow.next;
    fast = fast.next.next;
  }

  node = new TreeNode(slow.val, recurBuild(start, slow), recurBuild(slow.next, end));
  return node;
};

复杂度分析

• 时间复杂度： O(nlogn)
• 空间复杂度：O(logn) 二分递归

[hizhisong]

朴素二分递归

class Solution {
public:
    // Find midle
    // [a, b)
    ListNode* findMid(ListNode* head, ListNode* end) {
        ListNode *fast = head, *slow = head;
        while (fast != end && fast->next != end) {
            fast = fast->next;
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }

    TreeNode* buildTree(ListNode* head, ListNode* end) {
        // Recursive ending
        // Last recursion (when head->next == end), we donot do with findMid
        if (head == end) {
            return nullptr;
        }

        // 这种情况findMid处理了
        // if (head->next == end) {
        //     return new TreeNode(head->val);
        // }

        ListNode* mid = findMid(head, end);
        TreeNode* root = new TreeNode(mid->val);
        root->left  = buildTree(head, mid);
        root->right = buildTree(mid->next, end);

        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        // For "[]"
        if (head == nullptr){
            return nullptr;
        }

        return buildTree(head, nullptr);
    }
};

O(nlogn)

[xiezhengyun]

思路

• 一看题解才知道，快慢指针找链表中点，我是直接转数组了...

• 找中点，递归生成树

  /**
  * 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
  var arr = []
  while (head) {
  arr.push(head.val)
  head = head.next
  }
  
  var buildTree = function (arr, l, r) {
  if (l > r) return null
  var mid = Math.ceil((l + r) / 2)
  var root = new TreeNode(arr[mid])
  
  root.left = buildTree(arr, l, mid - 1)
  root.right = buildTree(arr, mid + 1, r)
  
  return root
  }
  return buildTree(arr, 0, arr.length - 1)
  };

  复杂度

  N是链表长度

• 时间复杂度 O(2N)
• 空间复杂度 O(N)

[Francis-xsc]

思路

快慢指针法找中点，递归构造树

代码

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return create(head,nullptr);
    }
    ListNode* findMiddleNode(ListNode* left,ListNode* right){
        ListNode* fast=left,*slow=left;
        while(fast!=right&&fast->next!=right)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
    TreeNode* create(ListNode* left,ListNode* right){
        if(left==right)
            return nullptr;
        ListNode* mid=findMiddleNode(left,right);
        return new TreeNode(mid->val,create(left,mid),create(mid->next,right));
    }
};

复杂度分析

• 时间复杂度：O(nlogN)
• 空间复杂度：O(nlogN)

[wangyifan2018]

/**
 * 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 {
    return buildTree(head, nil)
}

func buildTree(left, right *ListNode) *TreeNode {
    if (left == right){
        return nil
    }
    fast, slow := left, left
    for fast != right && fast.Next != right {
        fast = fast.Next.Next
        slow = slow.Next
    }
    mid := slow
    root := &TreeNode{mid.Val, nil, nil}
    root.Left = buildTree(left, mid)
    root.Right = buildTree(mid.Next, right)
    return root
}

[Moin-Jer]

思路

---

找到链中点作为根节点的值，将链表分为两部分，递归处理左右子树

代码

---

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        ListNode pre = null, h1 = head, h2 = head;
        while (h2 != null && h2.next != null) {
            pre = h1;
            h1 = h1.next;
            h2 = h2.next.next;
        }
        TreeNode root = new TreeNode(h1.val);
        pre.next = null;
        h2 = h1.next;
        h1 = head;
        root.left = sortedListToBST(h1);
        root.right = sortedListToBST(h2);
        return root;
    }
}

复杂度分析

---

• 时间复杂度： O(NlogN)，递归深度为 logn，每一层都需要遍历整个链表
• 空间复杂度： O(logn)

[user1689]

题目

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

思路

双指针

python

# 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:
        # time nlogn 每次找中点为n 递归次数logn
        # space logn 即树的高度
        # 思路一
        # 双指针

        # base
        if not head:
            return None
        elif not head.next:
            return TreeNode(head.val)

        # 找到中点
        pre = None
        slow, fast = head, head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next

        # 建立并断开前后连接点
        root = TreeNode(slow.val)
        pre.next = None

        # 递归建立左右子树
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

复杂度分析

• time nlogn 每次找中点为n 递归次数logn
• space logn

相关题目

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

[liuyangqiQAQ]

最简单的方法就是将链表转成list只需要遍历一遍即可

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList<>();
        for(ListNode node = head; node != null; node = node.next) {
            list.add(node.val);
        }
        return buildTree(list, 0, list.size() - 1);
    }
    public TreeNode buildTree(List<Integer> list, int left, int right) {
        if(left <= right) {
            int mid = left + (right - left) / 2;
            TreeNode node = new TreeNode(list.get(mid));
            node.left = buildTree(list, left, mid - 1);
            node.right = buildTree(list, mid + 1, right);
            return node;
        }
        return null;
    }
}

复杂度分析:

时间复杂度:O(n） 空间复杂度:O(N)

将他变成list无非是为了更方便的找中间点，如果不想开销额外的空间我们可以通过快慢指针每次都找出链表中间点也可以做到。

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null);
    }
    public TreeNode buildTree(ListNode head, ListNode endNode) {
        if(head != endNode) {
            ListNode midNode = getMidNode(head, endNode);
            TreeNode treeNode = new TreeNode(midNode.val);
            treeNode.left = buildTree(head, midNode);
            treeNode.right = buildTree(midNode.next, endNode);
            return treeNode;
        }
        return null;
    }
    //寻找中间节点
    public ListNode getMidNode(ListNode head, ListNode endNode) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != endNode && fast.next != endNode) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

复杂度分析:

时间复杂度:O(n） 空间复杂度:O(logn)

[Dana-Dai]

将有序链表变成有序数组，每次取mid作为根节点

/**
 * 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> res;
        while (head) {
            res.push_back(head->val);
            head = head->next;
        }
        return dfs(res, 0, res.size() - 1);
    }

    TreeNode* dfs(vector<int>& res, int start, int end) {
        if (start > end) return nullptr;
        int mid = start + (end - start >> 1);
        TreeNode* root = new TreeNode(res[mid]);

        root->left = dfs(res, start, mid - 1);
        root->right = dfs(res, mid + 1, end);
        return root;
    }
};

时间复杂度：O（n），链表转换为数组需O（n）内完成，而后的dfs则是O（logn） 空间复杂度：O（n），vector的加入

[xieyj17]

# 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: Optional[ListNode]) -> Optional[TreeNode]:
        val = []
        while head:
            val.append(head.val)
            head = head.next

        def to_BST(l, r):
            if l > r:
                return None
            elif l == r:
                return TreeNode(val[l])
            else:
                mid = (l+r) // 2
                node = TreeNode(val[mid])
                node.left = to_BST(l, mid-1)
                node.right = to_BST(mid+1, r)
                return node

        return to_BST(0, len(val)-1)

第一次接触binary tree， 看了答案才会做的

Time O(N)

Space O(N)

[ZJP1483469269]

思路

使用快慢指针找到链表中心，并加入树顶，将链表分成两个链表，重复前面过程

代码

class Solution {
public TreeNode sortedListToBST(ListNode head) {
    if(head==null) return null;
    if(head.next==null) return new TreeNode(head.val);
    ListNode l=head,h=head,pre =null;
    while(h.next!=null){
       h = h.next.next!=null?h.next.next:h.next;
       pre = l;
       l=l.next;
    }
    TreeNode root=new TreeNode(l.val);
    pre.next=null;
    ListNode rhead = l.next;

    root.left = sortedListToBST(head);
    root.right = sortedListToBST(rhead);
    return root;
}
}

复杂的分析

时间复杂度：O（Nlog2N） 空间复杂度：O（1）

[shixinlovey1314]

Title:109. Convert Sorted List to Binary Search Tree

Question Reference LeetCode

Solution

To make the tree a weighted binary tree, each time we need to make the middle point as the root node. So the problem is to find the middle point of the list, then recursively build its left subtree and right subtree.

Code

class Solution {
public:
    TreeNode* constructTree(ListNode* start,  ListNode* end) {  
        if (!start || !end)
            return NULL;

        TreeNode *node = new TreeNode();
        ListNode *pre = start, *slow = start, *fast = start;

        while (fast && fast != end) {
            pre = slow;
            slow = slow->next;
            fast = fast->next;
            if (fast && fast != end)
                fast = fast->next;
        }

        node->val = slow->val;
        node->left = pre == slow? NULL:constructTree(start, pre);
        node->right = slow == fast? NULL:constructTree(slow->next, end);  

        return node;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        ListNode* tail = head;
        while(tail && tail->next)
            tail = tail->next;
        return constructTree(head, tail);
    }
};

Complexity

Time Complexity and Explaination

O(nlogn)

Space Complexity and Explaination

O(logn)

[SunnyYuJF]

思路

快慢指针求中点，递归构建子树

代码 Python

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        root =self.buildTree(head,None)
        return root

    def getMid(self, left, right):
        fast, slow =left,left
        while fast!=right and fast.next!=right:
            slow = slow.next
            fast = fast.next.next
        return slow

    def buildTree(self, left, right):
        if left==right:
            return None
        mid = self.getMid(left, right)
        node = TreeNode(mid.val)
        node.left = self.buildTree(left, mid)
        node.right = self.buildTree(mid.next, right)
        return node

复杂度分析

时间复杂度： O(NlogN) 递归logN次
空间复杂度： O（logN）

[chun1hao]

var sortedListToBST = function(head) { 
    if(!head) return null
    let slow = head
    let fast = head
    let pre = null
    while(fast && fast.next){
        pre = slow
        slow = slow.next
        fast = fast.next.next
    }    
    let root = new TreeNode(slow.val)
    if(pre){
        pre.next = null
        root.left = sortedListToBST(head)
    }    
    root.right = sortedListToBST(slow.next)
    return root
};

时间： O(NlogN) 空间： O(logN)