【Day 9 】2024-04-16 - 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

[zhiyuanpeng]

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None
        nodes = []
        p = head
        while p:
            nodes.append(p.val)
            p = p.next
        root = self.sortedListToBSTHelper(nodes)
        return root

    def sortedListToBSTHelper(self, nodes):
        if nodes:
            mid = len(nodes) // 2
            root = TreeNode(val=nodes[mid])
            root.left = self.sortedListToBSTHelper(nodes[:mid])
            root.right = self.sortedListToBSTHelper(nodes[mid+1:])
            return root
        else:
            return None

time O(N), space O(N)

[RocJeMaintiendrai]

思路

快慢指针 + 递归

代码

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;

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

}

**复杂度分析**
- 时间复杂度：O(n)
- 空间复杂度：O(tree height)

[xil324]

**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    const arr = []; 
    while(head) {
        arr.push(head.val);
        head = head.next;
    }
    return createTree(arr, 0, arr.length-1);
};

function createTree(arr, left, right) {
    if(left > right) return null; 
    const mid = Math.floor((left + right)/2); 
    const node = new TreeNode(arr[mid]);
    if(left === right) return node;
    node.left = createTree(arr, left, mid -1);
    node.right = createTree(arr, mid + 1, right);
    return node; 
}

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

[Alexzhang-Mini]

class Solution:
    def findMiddle(self, head):
        if not head or not head.next:
            return head

        prev_ptr = None
        slow_ptr = head
        fast_ptr = head

        while fast_ptr and fast_ptr.next:
            prev_ptr = slow_ptr
            slow_ptr = slow_ptr.next
            fast_ptr = fast_ptr.next.next

        if prev_ptr:
            prev_ptr.next = None

        return slow_ptr

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

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

        if head == mid:  
            return root

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

        return root

[lxy1108]

思路

首先将链表转换为数组，方便后续直接访问元素。采用递归的方式构建树，由于需要构建平衡二叉树，因此树的根节点为有序数组的中间元素。

代码

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        nums = []
        p = head
        while p:
            nums.append(p.val)
            p = p.next
        def genTree(nums):
            if not nums:
                return None
            root_idx = len(nums)//2
            root = TreeNode(nums[root_idx])
            root.left = genTree(nums[:root_idx])
            root.right = genTree(nums[root_idx+1:])
            return root
        return genTree(nums)

复杂度分析

空间复杂度O(n),因为创建了一个新的数组

时间复杂度O(ln)，因为遍历了一遍链表

[Martina001]

思路：考察的是递归和分治，dfs更容易理解，类似于归并排序，每个节点都走进一次递归，一次递归每个节点又会被遍历logn次，时间复杂度为O(nlogn) dfsMid考察的是中序遍历，每个节点只会被遍历一次，时间复杂度为O(n)

public TreeNode sortedListToBST(ListNode head) {
        // 由于要找平衡二叉搜索树 所以直接找到中点后进行归并即可，但是链表不是数组（108 将有序数组转换为二叉搜索树），不能直接快速找到中点，
        // 所以只有递归采用中序遍历的方式，分治才可以保证On的复杂度，既然是中序并且分治 必然要先找到left 和right，right就是链表长度
        int n = 0;
        ListNode temp = head;
        while(temp!=null){
            n++;
            temp = temp.next;
        }
//        return dfs(head,0,n-1);
        headNode = head;
        return dfsMid(0,n-1);
    }

    private TreeNode dfsMid(int l,int r){
        // 学习一下题解中的中序遍历
        if(l>r){
            return null;
        }
        int mid =  (r-l)/2+l;
        TreeNode leftNode = dfsMid(l,mid-1);
        // 此时headNode就是当前的中点节点middleNode
        TreeNode midNode = new TreeNode(headNode.val);
        headNode = headNode.next;
        midNode.left = leftNode;
        midNode.right = dfsMid(mid+1,r);
        return midNode;
    }

    private TreeNode dfs(ListNode head,int left ,int right){
        // 递归结束条件 记得只要是递归分治，一定要考虑这个递归结束条件
        if(left>right){
            return null;
        }
        int mid = (right-left)/2+left;
        // 此时head需要来到链表中点的位置
        int moveNum = mid-left;
        ListNode cur = head;
        while(moveNum-- >0){
            cur = cur.next;
        }
        TreeNode root = new TreeNode(cur.val);
        root.left  = dfs(head,left,mid-1);
        root.right =  dfs(cur.next,mid+1,right);
        return root;
    }

[YANGLimbo]

已经忘了平衡二叉树的旋转知识点了，这里用标准思路，即利用链表不断从中间分开构成树

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        // 改天再学avl tree，现在先用推荐的思路，即寻找中点，递归构造树节点
        // 注意为了防止无限递归，断开链表
        if(head == nullptr){
            return nullptr;
        }else if(head->next == nullptr){
            TreeNode* node = new TreeNode(head->val);
            // 这个有没有内存问题？
            return node;
        }

        // 快慢指针法（龟兔赛跑）寻找链表中点，作为树节点的根部
        ListNode* fast = head;
        ListNode *slow = head;// 注意，ListNode* fast, *slow = head;只会给后者赋值，是错误的
        ListNode* prev = nullptr;

        while(fast!=nullptr && fast->next!=nullptr){
            /*确保两件事：
            fast 指针不是 nullptr，即它确实指向了一个有效的链表节点。
            fast->next 也不是 nullptr，这意味着 fast 指针所指向的节点后面至少还有一个节点。
            */
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }

        //断开链表
        if(prev!=nullptr){
            prev->next = nullptr;
        } // 这一步if是必要的，否则会出现尝试访问 prev->next 失败，程序崩溃

        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) {}
 * };
 */

[rao-qianlin]

思路： 递归构造子树，每次找到链表中点作为根节点 使用快慢指针找到链表中点

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

时间复杂度 O(N*logN)

[GReyQT]

题解思路：

1，分解子问题：每一次都是创建一个最小平衡二叉树 2，子问题推导递推公式： （0）首次左端为链表的头，右端为链表尾null 对于左子树，每一次递归，左端为链表的头，右端为中位数; 对于右子树，每一次递归，左端为中位数->next，右端为链表尾null； （1）获取中位数，作为根节点； （2）中位树数的左侧为，左子节点（左子树）；中位数的右侧为右子节点（右子树）； （3）每一个左子树和右子树，重复步骤（1）（2）； 3，判断递归终止条件：当左端等于右端时结束； 代码：

class Solution {
public:
    //快慢指针寻找中位数
    ListNode* find_mid(ListNode* left, ListNode* right)
    {
        ListNode* slow = left;
        ListNode* fast = left;
        while (fast != right && fast->next != right)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    TreeNode* creatree(ListNode* left, ListNode* right)
    {
        if(left == right)
        {
            return nullptr;
        }
        ListNode* mid = find_mid(left, right);
        TreeNode* root = new TreeNode(mid->val);
        root->left = creatree(left, mid);
        root->right = creatree(mid->next, right);
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head) 
    {
        return creatree(head,nullptr);
    }
};

复杂度分析：

• 时间复杂度：取决于链表的长度n，以及二分创建树的递归，因此时间的复杂度为O(nlog n)
• 空间复杂度：取决于链表的长度n，每一层递归创建一个新的树节点，因此空间复杂度为 O(log n)

[CathyShang]

思路：

• 找到链表中点
• 构造二叉数，左树先，递归

代码：

class Solution {
public:
    ListNode* median(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 = median(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) {
        // TreeNode* res = new TreeNode();

        // ListNode* preHead = new ListNode(-1);
        // preHead->next = head;
        // ListNode* cur = preHead->next;
        // ListNode* fast = cur;
        // if(head==nullptr) return res->left;
        // //遍历链表
        // while(cur!=nullptr){
        //     if(fast==nullptr){ 
        //         TreeNode* test = new TreeNode(cur->val);
        //         res->left = test;
        //         break;
        //     }           
        //     cur = cur->next;
        // }

        // return res;
        return buildTree(head, nullptr);

    }
};

复杂度：

• 时间复杂度$O(NlogN)$
• 空间复杂度$O(logN)$

[Dtjk]

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        TreeNode *root;
        if (head == nullptr) return nullptr;
        else if (head->next == nullptr) {
            root = new TreeNode(head->val);
            return root;
        }

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

        while (pre->next != slow) pre = pre->next;
        root = new TreeNode(slow->val);
        pre->next = nullptr; 
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);

        return root;

    }
};

[pandapls]

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

    let slow = head;
    let fast = head;
    let preSlow; //缓存slow前一个节点

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

    const root = new TreeNode(slow.val);
    if (preSlow) {
        preSlow.next = null;
        root.left = sortedListToBST(head)
    }

    root.right = sortedListToBST(slow.next)

    return root
};

复杂度分析

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