azl397985856 commented 2 years ago

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

zjsuper commented 2 years ago

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

        while quick and quick.next:
            pre = slow
            slow = slow.next
            quick = quick.next.next
        #print(pre==head)
        if pre:
            pre.next = None
        a = TreeNode(slow.val)
        if quick == slow:
            return a

        a.left = self.sortedListToBST(head)
        a.right = self.sortedListToBST(slow.next)
        return a

Ellie-Wu05 commented 2 years ago

思路一： linked list换成sorted list

先去做了108 Convert Sorted Array to Binary Search Tree

代码

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

        def buildBSTfromList(nums,l,r) -> TreeNode:

            if l>r:
                return None
            m = l + (r-l)//2
            root = TreeNode(nums[m])
            root.left = buildBSTfromList(nums,l,m-1)
            root.right = buildBSTfromList(nums,m+1,r)

            return root

        res = []
        while head:
            res.append(head.val)
            head = head.next

        return buildBSTfromList(res,0,len(res)-1)

复杂度

时间：On / 空间：On

思路二：双指针

思路我有了，但是代码一直没搞明白 / 答案参考了评论区，官方题解 / 还是要多多学习 /

代码

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

        if not head:
            return head

        pre = None
        slow = head
        fast = head

        # 找中间节点
        while fast and fast.next:
            fast = fast.next.next
            pre = slow
            slow = slow.next

        # 如果slow = head的情况：
        if pre:
            pre.next = None

        node = TreeNode(slow.val)

        if slow == fast:
            return node

        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(slow.next)

        return node

复杂度分析

令 n 为链表长度。 /

时间复杂度：递归树的深度为 logn，每一层的基本操作数为 n，因此总的时间复杂度为O(nlogn)O /

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

currybeefer commented 2 years ago

思路：参考官方题解，由于链表已经排序了，所以以寻找到链表的中点，以链表中点为界限，中点左边是二叉搜索树的左孩子们，中点的右边是二叉树的右孩子们。进行递归地构造。寻找链表的中点当然就用快慢指针法就好啦。 TreeNode sortedListToBST(ListNode head) { if(head==nullptr) return nullptr; return sortedListToBST(head,nullptr); } TreeNode sortedListToBST(ListNode head, ListNode tail) { if(head==tail) return nullptr; ListNode slow=head; ListNode fast=head; //寻找链表中点，以中点为界构造二叉树 while(fast!=tail && fast->next!=tail) { fast=fast->next->next; slow=slow->next; } TreeNode root=new TreeNode(slow->val); root->left=sortedListToBST(head,slow); root->right=sortedListToBST(slow->next,tail); return root; } 复杂度分析：时间复杂度为O(nlogn) 空间复杂度为O(logn)

maybetoffee commented 2 years ago

双指针找终点

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return build(head, null);
    }
    //[start, end) 
    TreeNode build(ListNode start, ListNode end){
        if(start == end){
            return null;
        }

        ListNode mid = findMid(start, end);
        TreeNode root = new TreeNode(mid.val);
        root.left = build(start, mid);
        root.right = build(mid.next, end);
        return root;
    }
    //two pointers
    ListNode findMid(ListNode start, ListNode end){
        ListNode slow = start, fast = start;
        while (fast != end && fast.next != end){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

forestie9 commented 2 years ago

Ideas

Use the list middle value as root, then recursively build the tree. Note the base case where only one element left in the recursion and should return node.

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        value = []
        while head:
            value.append(head.val)
            head = head.next    

        def convertBST(l, r):
            if l > r: return None
            mid = (l + r) // 2
            node = TreeNode(value[mid])

            if l == r: return node # base case

            node.left = convertBST(l, mid - 1)
            node.right = convertBST(mid + 1, r)
            return node

        return convertBST(0, len(value)-1)

O(n) time and space

KelvinG-LGTM commented 2 years ago

思路

线索: BST + 高度平衡. 意味着左右两边的节点个数一致. 自然想到用递归的解法,

递归函数的定义: 返回一个高度平衡的BST.

递归函数的思路: 先找到中间点, 递归地把中间点的左边接到中间点的left. 把中间点的右边接到中间点的right.

易错点: 每次递归调用时, 左侧的部分需要"剪断". 既, 应该剪断左侧部分与当前中间点的联系. pre.next = None 不然会进入死循环.

代码

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head: 
            return None
        if not head.next: 
            return TreeNode(head.val)
        # Find mid first
        slow, fast = head, head
        dummy = TreeNode()
        dummy.next = head
        pre = dummy
        while fast and fast.next: 
            pre = pre.next
            slow = slow.next
            fast = fast.next.next
        # Slow is mid or left_mid
        root = TreeNode(slow.val)
        pre.next = None
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)

        return root

复杂度分析

时间复杂度

O(NlogN) - 每一层是操作数N * 层数logN

空间复杂度

O(logN): 递归树的高度

houmk1212 commented 2 years ago

思路

根据二叉搜索树的性质，升序链表的中间节点一定是一个局部二叉搜索子树的根。因此，可以先找到链表的中间节点，然后再递归构建树结构。

代码

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return binaryCreate(head, null);
    }
    public TreeNode binaryCreate(ListNode l, ListNode r) {
        if (l == null || l == r)
            return null;
        if (l.next == null || r == l.next)
            return new TreeNode(l.val);
        ListNode slow = l;
        ListNode fast = l;
        while (fast != r && fast.next != r) {
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = binaryCreate(l, slow);
        root.right = binaryCreate(slow.next, r);
        return root;
    }
}

复杂度

时间复杂度：O(NlogN)
空间复杂度： O(logN)

xingchen77 commented 2 years ago

思路

寻找中间节点的位置，左右节点递归

代码

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

复杂度

时间 O(nlog(n)) \ 空间 O(log(n))

MoonLee001 commented 2 years ago

思路

1.利用双指针找到链表的中间节点作为root 2.利用中间节点断开链表 3.分别在左右两部分链表进行从步骤1开始递归操作

代码

var sortedListToBST = function(head) {
    if (head == null) {
        return null;
    }

    let pre = null;
    let slow = fast = head;

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

    if (pre != null) {
        pre.next = null;
    } else {
        head = null;
    }
    const next = slow.next;
    slow.next = null;
    const root = new TreeNode(slow.val);
    root.left = sortedListToBST(head);
    root.right = sortedListToBST(next);
    return root;
};

复杂度分析

时间复杂度： O(nlogn)
空间复杂度： O(logn)

Magua-hub commented 2 years ago

思路找中点后递归 + 中序遍历

代码


class Solution {
public:
    ListNode* h; 
    TreeNode* sortedListToBST(ListNode* head) {
        //if(!head ) return head;
        h = head;
        int n = 0;
        for(auto p = head; p; p = p->next) n ++;
        return build(0, n - 1);

    }

    TreeNode* build(int l, int r) {
        if(l > r) return nullptr;
        TreeNode *root = new TreeNode();
        int mid = (l + r  +1) >> 1;
        root->left = build(l, mid - 1);
        root->val = h->val;   
        h = h->next; 
        root->right = build(mid + 1, r);
        return root;
    }
};
复杂度
时间复杂度：O(nlogn)
空间复杂度： O(logn)

zqwwei commented 2 years ago

code

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

    while(fast!=tail&&fast.next!=tail){
        fast = fast.next.next;
        slow = slow.next;
    }
    TreeNode thead = new TreeNode(slow.val);
    thead.left = toBST(head,slow);
    thead.right = toBST(slow.next,tail);
    return thead;
}

carterrr commented 2 years ago

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

}

zzz607 commented 2 years ago

思路

有二种基本思路：

将链表转换为数组，然后按二分法进行递归
不转换为链表，每次都遍历链表找中点，按中点分为左右二个子链表递归

第一种思路相当于使用空间换时间，时间复杂度为O(N) + O(N) = O(N)，第一O(N)为转换为链表的过程，第二个为构造树的过程
第二种思路的时间复杂度为O(NlogN)

代码

func sortedListToBST(head *ListNode) *TreeNode {
    var buildBST func([]int) *TreeNode
    buildBST = func(data []int) *TreeNode {
        if data == nil || len(data) == 0 {return nil}

        rootIdx := len(data) / 2
        root := &TreeNode{Val: data[rootIdx]}
        if rootIdx > 0 {
            root.Left = buildBST(data[:rootIdx])
        }
        if rootIdx < len(data) - 1 {
            root.Right = buildBST(data[rootIdx + 1:])
        }

        return root
    }

    var arr []int
    for head != nil {
        arr = append(arr, head.Val)
        head = head.Next
    }
    return buildBST(arr)
}

复杂度分析

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

YuyingLiu2021 commented 2 years ago

先找出链表的中点 然后再建树 （中点就是树的根）
时间复杂度: O(NlogN) 
空间复杂度: O(logN)

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

        def findmid(start, end):
            slow = start
            fast = start

            while fast != end and fast.next != end:
                slow = slow.next
                fast = fast.next.next
            return slow

        def buildtree(start, end):
            if start == end:
                return

            mid = findmid(start, end)

            root = TreeNode(mid.val) #root = TreeNode(findmid(start, end).val)
            root.left = buildtree(start, mid)
            root.right = buildtree(mid.next, end)

            return root
        return buildtree(head, None)

revisegoal commented 2 years ago

二分 or 快慢指针

递归找中点作为根节点创建二叉树，有两种方式：

数组二分，空间换时间
每次递归都使用快慢指针找中点

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        return buildTree(0, list.size() - 1, list);
    }   

    TreeNode buildTree(int left, int right, List<Integer> list) {
        if (left > right) {
            return null;
        }
        int mid = left + (right - left + 1) / 2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = buildTree(left, mid - 1, list);
        root.right = buildTree(mid + 1, right, list);
        return root;
    }
}

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

rzhao010 commented 2 years ago

Thoughts

Split the linkedlist intor three parts:

the mid node, which will be the root of tree
the left part, will be left subtree
the right part, will be right subtree Use fast and slow pointers to locate the mid point(root), use recursion to genarate left and right subtrees

Code

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

        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = slow;
        while (fast != null && fast.next != null) {
            pre = slow; // pre is the previous node of slow
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.right = sortedListToBST(slow.next);
        slow.next = null;
        pre.next = null;
        root.left = sortedListToBST(head);
        return root;
    }

Complexity

Time: O(nlogn), each level traverse n/2, logn is the height of tree
Space: O(logN), height of the tree

caterpillar-0 commented 2 years ago

思路

快慢指针找中位数+递归建树；

代码

class Solution {
public:
    //快慢指针找中位数，递归确定树的结构，从根节点开始
    //左闭右开，因为链表，上一个节点不好找
    //1、找中位数，在链表中,快慢指针
    ListNode* findMid(ListNode* left,ListNode* right){
        ListNode* low=left;
        ListNode* fast=left;
        while(fast!=right && fast->next!=right){
            fast=fast->next->next;
            low=low->next;
        }
        return low;
    }
    //2、形成递归，依次构建树节点
    TreeNode* findRoot(ListNode* left,ListNode* right){
        //递归结束条件
        if(left==right){
            return nullptr;
        }
        ListNode* mid=findMid(left,right);
        TreeNode* root=new TreeNode(mid->val);//mid是链表节点指针，用值创建根节点
        root->left=findRoot(left,mid);//左闭右开
        root->right=findRoot(mid->next,right);
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        return findRoot(head,nullptr);
    }
};

复杂度分析

时间复杂度：T(n)=2T(n/2)+o(n);=o(nlog(n));
空间复杂度：o(log(n)),平衡二叉树的深度为这个，因此空间复杂度为o(logn)

kite-fly6618 commented 2 years ago

思路：

找到中间节点，构造二叉搜索树

代码：

const sortedListToBST = (head) => {
  const arr = [];
  while (head) { // 将链表节点的值逐个推入数组arr
    arr.push(head.val);
    head = head.next;
  }
  // 根据索引start到end的子数组构建子树
  let buildBST = function(start,end) {
      if (start>end) return null
      let mid = (start+end) >>> 1
      let root = new TreeNode(arr[mid])
      root.left = buildBST(start,mid-1)
      root.right = buildBST(mid+1,end)
      return root
  }
  return buildBST(0,arr.length-1)
};

复杂度：

时间复杂度: O(nlogn)
空间复杂度: O(logn)

physicshi commented 2 years ago

思路

rust版本，递归数组，取中间节点，构建bst

代码

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn sorted_list_to_bst(mut head: Option<Box<ListNode>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut stack = Vec::new();
        // 收集链表节点值
        while let Some(node) = head {
            stack.push(node.val);
            head = node.next;
        }
        Solution::s(&stack[..])
    }
    pub fn s(nums: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
        let mut n = nums.len();
        if n == 0 {
            return None;
        }
        let mid = n / 2;
        let mut node = TreeNode::new(nums[mid]);
        // 递归创建左子树
        node.left = Solution::s(&nums[..mid]);
        // 递归创建右子树
        node.right = Solution::s(&nums[mid + 1..]);
        Some(Rc::new(RefCell::new(node)))
    }
}

复杂度

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

LyuliangLiu commented 2 years ago

Idea

Recursive. For every list, use fast-slow pointers to find the mid one as root. Do the same for left half of the list; Do the same for the right half.

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;
        ListNode slow = head;
        ListNode preMid = null;
        while (fast != null && fast.next != null) {
            fast = fast.next;
            fast = fast.next;
            preMid = slow;
            slow = slow.next;
        }
        preMid.next = null;
        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}

Complexity

Time: O(NlogN) Space: O(logN) for recursion.

yz3516 commented 2 years ago

Idea

用recursion来做，先找到中点，然后左半边和右半边都call自己来construct

Code

    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        return constructBST(0, checkLength(head) - 1, head);
    }

    private int checkLength(ListNode head){
        if(head == null) return 0;
        return checkLength(head.next) + 1;
    }

    private TreeNode constructBST(int start, int end, ListNode head){
        if(start > end) return null;

        int mid = start + (end - start) / 2;
        ListNode temp = head;

        for(int i = 0; i < mid; i++){
            temp = temp.next;
        }
        TreeNode root = new TreeNode(temp.val);
        root.left = constructBST(start, mid - 1, head);
        root.right = constructBST(mid + 1, end, head);
        return root;
    }

Complexity

Time: O(n), 因为要遍历所有节点找到长度，再找到中点；\ Space: O(logn), 每次同时call左右，recursion的次数是树的高度。

wwang4768 commented 2 years ago

Idea
Use vector to facilitate calculations in left and right branches via a mid point

Code

class Solution {
public:
    vector<int>v;
    TreeNode*balance(vector<int>v){
        if(v.size()==0){
            return NULL;
        }
        if(v.size()==1){
            return new TreeNode(v[0]);
        }
        int mid = v.size()/2;
        TreeNode* node = new TreeNode(v[mid]);
        vector<int>lnode(v.begin(), v.begin()+mid);
        vector<int>rnode(v.begin()+mid+1, v.end());
        node->left = balance(lnode);
        node->right = balance(rnode);
        return node;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        while(head){
            v.push_back(head->val);
            head=head->next;
        }
        return balance(v);

    }
};

Complexity
Time: Memory:

CarrieyqZhang commented 2 years ago

思路

recursive method to create tree -> sortedListBST(ListNode head)
    - if head = null, return null
    - find mid Node: call getMid(head)
    - create root with value of mid.val
    - if head = mid, just return root
    - root.left = recursive call sortedListToBST(head)
    - root.right = recursive call sortedListToBST(mid.next)

Find mid and break previous links ->getMid(ListNode head)
    - initialize slow, fast, prev to head
    - while (fast not null && fast.next not null)
        - prev = slow;
        -slow = slow.next;
        - fast = fast.next.next;
    -break the link if prev != null
    -return slow

代码

public TreeNode sortedListToBST(ListNode head) {

        if(head == null) return null;

        ListNode mid = getMid(head);
        TreeNode root = new TreeNode(mid.val);

        if(head == mid)
            return root;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
        return root;       
    }

    public ListNode getMid(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = head;
        while(fast != null && fast.next != null){
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //break the link before the mid point
        if(prev != null)
            prev.next = null;
        return slow;
    }

复杂度分析

时间复杂度：O(NlogN)
空间复杂度：O(logN)

Davont commented 2 years ago

code

var sortedListToBST = function (head) {
  if (!head) return null;
  return dfs(head, null);
};

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

xixiao51 commented 2 years ago

思路

快慢指针找链表中点，然后通过递归得到左子树和右子树。

代码

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

复杂度

时间复杂度：O(nlogn)，其中 n 是链表的节点数量
- n + 2 n/2 + 4 n/4 + ... + n n/n = n logn (二叉树的高度为logn)
空间复杂度：O(logn) 递归的深度

fhuang5 commented 2 years ago

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        int count = 0;
        ListNode cur = head;
        while (cur!= null){
            cur = cur.next;
            count++;
        }
        cur = head;
        for (int i = 0; i< count/2-1; i++){
            cur = cur.next;
        }
        TreeNode root = new TreeNode(cur.next.val);
        root.right= sortedListToBST(cur.next.next);
        cur.next = null;
        root.left = sortedListToBST(head);
        return root;     

    }
}

//TC: O(N logN) where N is the length of the linked list.
//SC: O(Log N) on call stack, and O(N) on the heap.

wenliangchen commented 2 years ago

思路

用双指针方法来找出链表的中间元素, 断开中间元素左边的链表部分作为左子树，同理右半边为右子树。

代码

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

        if(head == mid){
            return root;
        }

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

        return root;

    }

    private ListNode findMid(ListNode head){
        ListNode s = head, p = null, f = head;

        while(f!=null && f.next!=null){
            p = s;
            s = s.next;
            f = f.next.next;

        }

        if(p!=null){
            p.next = null;
        }

        return s;

    }
}

复杂度

-TC: O(N logN) -SC: O(Log N)

Geek-LX commented 2 years ago

4.9

思路：

快慢指针起初都指向头结点，分别一次走两步和一步，当快指针走到尾节点时，慢指针正好走到链表的中间。断成两个链表，分而治之。

代码：

#快慢指针法
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return head
        pre, slow, fast = None, head, head

        while fast and fast.next:
            fast = fast.next.next
            pre = slow #保存slow前一个节点，因为链表没有前驱指针
            slow = slow.next 

        if pre: #如果pre有值，则slow左边有节点
            pre.next = None #切断pre

        node = TreeNode(slow.val) # 根据slow指向的节点值，构建节点

        if slow == fast: #？？？
            return node
        node.left = self.sortedListToBST(head) #递归构建左子树
        node.right = self.sortedListToBST(slow.next) #递归构建右子树
        return node

复杂度：

令 n 为链表长度。

时间复杂度：递归树的深度为 lognlogn，每一层的基本操作数为 nn，因此总的时间复杂度为O(nlogn)O(nlogn)
空间复杂度：空间复杂度为O(logn)O(logn)

//存在疑问：应该是不了解递归树

4.9小结

1.知道了通过快慢指针找到中点和结尾

2.我知道左子树小于节点，右子树大于节点，但代码中封装好了，NEXT：预习树

node.left = self.sortedListToBST(head)

node.right = self.sortedListToBST(slow.next)

\3. slow和fast没有变化，这句代码不可少，需要提问

if slow == fast:

return node

4.python return?//函数当然有，怎么if里也有？

5.？复杂度计算不太理解

计算机生成了可选文字: Python 函数可以返回多种类型的值与其他编程语言不同， python 函数不限于返回单一类型的值。如果您昏它没有任何有关它可以返回的内容的信息。让我们看一个示例，其中函数将返回多种类型的值。 def get_demo_data(object_type): if ' s t r ' object_type ： return 'test' elif 'tuple' object_type: （ 1 ， 2 ， 3 ） object_type: [ 1 ， 2 ， 3 ] object_type ： None return elif ' 1 i s t ' return elif ' d i c t ' return else: return

「手画图解」三种解法逐个吃透 | 109. 有序链表转换二叉搜索树

来自 https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/shou-hua-tu-jie-san-chong-jie-fa-jie-zhu-shu-zu-ku/

zhiyuanpeng commented 2 years ago

class Solution:

    def tolist(self, head):
        val = []
        while head:
            val.append(head.val)
            head = head.next
        return val

    def genTree(self, vals, start, end):

        if start > end:
            return None
        mid = (start + end)//2
        node = TreeNode(val=vals[mid])
        if start == end:
            return node
        node.left = self.genTree(vals, start, mid-1)
        node.right = self.genTree(vals, mid+1, end)
        return node

    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        vals = self.tolist(head)
        return self.genTree(vals, 0, len(vals)-1)

oneline-wsq commented 2 years ago

思路

先将链表转为list，再进行迭代。

代码

# 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]:

        if not head:
            return None
        # 先计算出链表的长度
        p1=head
        n=0.0
        data=[]
        while p1:
            data.append(p1.val) # 将数据存到list中
            p1=p1.next 
            n+=1

        def buildT(arr):
            nn=float(len(arr))
            mm=int(nn/2+0.5)

            if nn<=0:
                return None

            mnode=TreeNode(val=arr[mm-1])
            mnode.left=buildT(arr[0:mm-1])
            mnode.right=buildT(arr[mm:int(nn)])

            return mnode    

        return buildT(data)

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

m908 commented 2 years ago

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }

        if (head->next == nullptr) 
        {
            return new TreeNode(head->val);
        }

        ListNode *p = head, *q = head, *pre = nullptr;
        while (q != nullptr && q->next != nullptr) 
        {
            pre = p;
            p = p->next;
            q = q->next->next;
        }
        pre->next = nullptr;

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

ShawYuan97 commented 2 years ago

前置知识

快慢指针
二叉搜索树，左子树小于根节点小于右子树，而且是平衡的

公司

暂无

思路

使用快慢指针，找到链表的中点，那么这就是树的根节点；
该节点左边就是左子树，对于左子树，再使用快慢指针，就能发现左子树根节点；
右子树同理；

关键点

快慢指针，三个指针pre,slow,fast
树的递归
边界判断

代码

语言支持：Python3

Python3 Code:


# 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]:
        """
        将有序链表变换为二叉搜索树

        Args:
            head(ListNode):头节点
        Returns:
            new_head(ListNode):返回新的头节点
        """
        """
        使用快慢指针，找到链表的中点，那么这就是树的根节点；  
        该节点左边就是左子树，对于左子树，再使用快慢指针，就能发现左子树根节点；  
        右子树同理；  
        """
        if not head:
            return head
        pre,slow,fast = None,head,head
        while fast and fast.next:
            fast = fast.next.next
            pre = slow
            slow = slow.next
        if pre:
            pre.next = None
        node = TreeNode(slow.val)
        if slow == fast:
            return node
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(slow.next)
        return node

复杂度分析

令 n 为数组长度。

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

思路

因为在链表中，找到中间节点的时间复杂度为O(n),如果换成数组，就可以在O(1)时间复杂度内找到中点；
这也是一种空间换时间的方法

关键点

递归函数调用时，边界要保持一直，左闭右开、左闭右闭、左开右闭

代码

语言支持：Python3

Python3 Code:


# 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]:
        """
        将有序链表变换为二叉搜索树

        Args:
            head(ListNode):头节点
        Returns:
            new_head(ListNode):返回新的头节点
        """
        def dfs(nodeList,l,r):
            # 这里设计一个递归的边界问题，
            # 例如：这里规定的区间是左闭右开的，那么l一定要小于r；
            # 而且每次递归调用时，都是遵循左闭右开的原则
            if l>=r:
                return 
            mid = int((r+l)/2)
            root = TreeNode(nodeList[mid])
            root.left = dfs(nodeList,l,mid)
            root.right =dfs(nodeList,mid+1,r)
            return root 
        nodeList = []
        while head:
            nodeList.append(head.val)
            head = head.next
        return dfs(nodeList,0,len(nodeList))

复杂度分析

令 n 为数组长度。

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

hyh331 commented 2 years ago

Day9 思路

找到中点后递归+中序遍历

代码

class Solution {
public:
    ListNode* h; 
    TreeNode* sortedListToBST(ListNode* head) {
        //if(!head ) return head;
        h = head;
        int n = 0;
        for(auto p = head; p; p = p->next) n ++;
        return build(0, n - 1);

    }

    TreeNode* build(int l, int r) {
        if(l > r) return nullptr;
        TreeNode *root = new TreeNode();
        int mid = (l + r  +1) >> 1;
        root->left = build(l, mid - 1);
        root->val = h->val;   
        h = h->next; 
        root->right = build(mid + 1, r);
        return root;
    }
};

复杂度分析

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

sallyrubyjade commented 2 years ago

思路

递归建立左右子树

代码

/**
 * 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 == null) return null;
    let len = 0;
    let h = head;  
    while (head) { 
        len++;
        head = head.next;
    }

    const buildBST = (start, end) => {
        if (start > end) return null;     
        const mid = (start + end) >>> 1;  
        const left = buildBST(start, mid - 1); 

        const root = new TreeNode(h.val);      
        h = h.next;                
        root.left = left;  

        root.right = buildBST(mid + 1, end);
        return root;
    };

    return buildBST(0, len - 1);
};

复杂度分析

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

youxucoding commented 2 years ago

4月9日

【day09】

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

难度中等

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

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

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

思路：

由于BST的性质可知，BST的中序遍历是单调递增的，题目中也说明了元素顺序递增，这样一来中序遍历构造二叉树即可，额外使用left,right,mid 三个元素规划左右子树空间，这样便免去寻找根节点的过程，借助一个辅助变量在链表中由前向后取值即可(链表顺序即为中序顺序)。

代码实现：

class Solution {
    ListNode node;
    public TreeNode sortedListToBST(ListNode head) {
        node = head;
        ListNode cur = head;
        int len = 0;
        while(cur != null){
            len++;
            cur = cur.next;
        }
        return traverse(0,len-1);
    }
    TreeNode traverse(int left,int right){
        if(left > right){
            return null;
        }
        int mid = (left+right)/2;
        TreeNode root = new TreeNode();
        root.left = traverse(left,mid-1);
        root.val = node.val;
        node = node.next;
        root.right = traverse(mid+1,right);
        return root;
    }
}

复杂度分析：

时间复杂度：O(N)
空间复杂度：O(logN)

zhulin1110 commented 2 years ago

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

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

题目描述

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

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

 

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []
输出: []

 

提示:

head 中的节点数在[0, 2 * 104] 范围内
-105 <= Node.val <= 105

前置知识

二叉搜索树
递归

思路1

观察题目发现，升序排列的链表相当于二叉树的中序遍历，其中根节点正好处于中间节点处，由此想到快慢指针可以用于找中间节点，快指针一次前进两节点，慢指针一次前进一个节点，当快指针到达尾节点处时，慢指针恰好处于中间节点。以上思路确定根节点
由于二叉搜索树的左子树节点都小于根节点，右子树节点都大于根节点。链表恰好是升序排列，中间节点的左侧均小于中间节点，中间节点的右侧均大于中间节点，创建左右子树即可。

代码1

语言支持：JavaScript

JavaScript Code:


/**
 * 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;
    return dfs(head,null);
};
function dfs(head, tail) {
    if (head == tail) {
        return null;
    }
    let fast = head;
    let slow = head;
    while (fast != tail && fast.next != tail) {
        fast = fast.next.next;
        slow = slow.next;
    }
    let root = new TreeNode(slow.val);
    root.left = dfs(head, slow);
    root.right = dfs(slow.next, tail);
    return root;
}

复杂度分析1(不太会。。。)

令 n 为链表长度。

时间复杂度：$O(nlog(n))$ 递归树的深度为 lognlogn，每一层的基本操作数为 nn，因此总的时间复杂度为O(nlogn)
空间复杂度：$O(log(n))$

webcoder-hk commented 2 years ago

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if head is None:
            return head
        d = []
        node = head
        while node is not None:
            d.append(node.val)
            node = node.next
        return self.buildTree(d)

    def buildTree(self, d):
        if len(d) == 0:
            return None
        mid = len(d)//2
        r = TreeNode(d[mid])
        r.left = self.buildTree(d[:mid])
        r.right = self.buildTree(d[mid+1:])
        return r

time: O(n) space: O(n)

liuguang520-lab commented 2 years ago

思路

使用快慢指针找出中点所在的位置，将其作为节点建树

class Solution {
public:
    ListNode* getMedian(ListNode* left, ListNode* right) {
        ListNode* fast = left;
        ListNode* slow = left;
        while (fast != right && fast->next != right) {
            fast = fast->next;
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }

    TreeNode* buildTree(ListNode* left, ListNode* right) {
        if (left == right) {
            return nullptr;
        }
        ListNode* mid = getMedian(left, right);
        TreeNode* root = new TreeNode(mid->val);
        root->left = buildTree(left, mid);
        root->right = buildTree(mid->next, right);
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        return buildTree(head, nullptr);
    }
};

复杂度分析

时间复杂度O(nlogn)
时间复杂度O(logn)

JasonHe-WQ commented 2 years ago

思路：说实话，我一开始根本没有思路，这类递归都不太会我看了l神的答案，觉得题目难点就在于要想到递归代码：


# 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]:
        l = 0
        stack = []
        cut, slow, fast = None, head, head
        if not head:
            return head
        while fast and fast.next:
            cut = slow
            slow = slow.next           
            fast = fast.next.next
        if cut:
            cut.next = None   
        midTree = TreeNode(slow.val)
        if slow==fast:
            return midTree
        midTree.left = self.sortedListToBST(head)
        midTree.right = self.sortedListToBST(slow.next)
        return midTree

577961141 commented 2 years ago

题目思路

解法一：快慢指针

获取当前链表的中点
以链表中点为根
中点左边的值都小于它，可以构造左子树
同理构造右子树
循环第一步

具体：

定义一个快指针和一个慢指针，快指针步数为2，慢指针步数为1
当快指针到达尾部的时候，慢指针正好指到的点为中点

解法二：缓存法

以空间换时间，用一个数组存储链表的节点
然后去数组的中间点建立树
左右两边的子树按照这个方式遍寻

题目的题解code

解法一

<?php

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @return TreeNode
     */
    function sortedListToBST($head)
    {
        if (!$head) {
            return null;
        }
        return $this->dfs($head, null);
    }

    /**
     * @param ListNode $head 头结点
     * @param ListNode $tail 尾节点
     * @return TreeNode|null
     */
    private function dfs($head, $tail)
    {
        if ($head == $tail) { // 这个的作用是头尾节点相等的时候就不用遍寻了，说明就没有了
            return null;
        }

        $fast = $head; // 快指针
        $slow = $head; // 慢指针
        while ($fast != $tail && $fast->next != $tail) { // 兼容奇数和偶数
            $fast = $fast->next->next;
            $slow = $slow->next;
        }
        $root = new TreeNode($slow->val);
        $root->left = $this->dfs($head, $slow);
        $root->right =$this->dfs($slow->next, $tail);

        return $root;
    }
}

解法二

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @return TreeNode
     */
    function sortedListToBST($head)
    {
        $res = [];
        while ($head) {
            $res[] = $head->val;
            $head = $head->next;
        }
        return $this->dfs($res, 0, count($res) - 1);
    }

    private function dfs($res, $l, $r)
    {
        if ($l > $r) {
            return null;
        }
        $mid = ceil(($r - $l)/2) + $l;
        $root = new ListNode($res[$mid]);
        $root->left = $this->dfs($res, $l, $mid-1);
        $root->right = $this->dfs($res, $mid+1, $r);
        return $root;
    }
}

时间和空间复杂度

解法一：

时间复杂度：递归树的深度为 lognlogn，每一层的基本操作数为 nn，因此总的时间复杂度为O(nlogn)
空间复杂度：空间复杂度为O(logn)
解法二：
时间复杂度：递归树每个节点的时间复杂度为 O(1)，每次处理一个节点，因此总的节点数就是 nn，也就是说总的时间复杂度为O(n)。
空间复杂度：使用了数组对链表的值进行缓存，空间复杂度为O(n)

yinhaoti commented 2 years ago

# 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]:
        """
        Keywords: LinkedList, BST, convert
        Ideas: 
            recurssion
            get mid value
            fast & slow pointer -> build treeNode
        TC: O(logn * n) = O(nlogn)
        SC: O(logn * 1) = O(logn)
        """
        def dfs(head, tail):
            if head == tail: return None
            slow, fast = head, head
            while fast!= tail and fast.next != tail:
                fast = fast.next.next
                slow = slow.next
            root = TreeNode(slow.val)
            root.left = dfs(head, slow)
            root.right = dfs(slow.next, tail)
            return root
        if not head: return head
        return dfs(head, None)

    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        """
        Use list to improve, no need find mid value in linkedlist
        Improve: O(n)

        TC: O(n)
        SC: O(n)
        """
        res = []
        while head:
            res.append(head.val)
            head = head.next

        def dfs(res, l, r):
            if l > r: return None
            m = (l + r) // 2
            root = ListNode(res[m])
            root.left = dfs(res, l, m - 1)
            root.right = dfs(res, m + 1, r)
            return root

        return dfs(res, 0, len(res) - 1)

C2tr commented 2 years ago

class Solution:
    def __init__(self):
        self.head = None
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        n, self.head = 0, head
        while head:
            head = head.next
            n += 1
        return self.to_bst(0, n - 1)
    def to_bst(self, left, right):
        if left > right: return
        m = (left + right) // 2
        left_child = self.to_bst(left, m - 1)
        father = TreeNode(self.head.val)
        self.head = self.head.next
        father.left = left_child
        father.right = self.to_bst(m + 1, right)
        return father

flaming-cl commented 2 years ago