专栏首页机器学习与推荐算法LeetCode109:有序列表转二叉搜索树

LeetCode109:有序列表转二叉搜索树

题目描述

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

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

题目链接:

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

样例

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

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

      0
     / \
   -3   9
   /   /
 -10  5

解题思路及代码

第一、我们要明白什么是BST。题目中描述了,所谓的二叉搜索树是一种对所有结点左右子树深度都不超过1,且左子树值都不超过根结点的值,右子树的值都不小于根结点的值。

第二、明确题目中给出的单链表是升序。

那么,我们无非需要找到单链表中的中间结点的值,然后依次递归迭代的构建出左右子树。

因此,我们重点解决的问题就是从单链表中找到中间结点

因为是单链表结构,并不是数组结构,所以查找中间结点需要进行遍历查找才行。那么我们是不是可以将单链表结构的数据转换成数组结构呢?这样岂不是查找起来比较容易吗?

由此思路,我们可以先遍历一遍单链表,然后构造出来一个数组,找到中间元素,再迭代构建数组的左右元素即可。具体代码如下:

# 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:
        # 采用递归的方式进行求解,由于是已经排序好的单链表,首先获取全部的排序元素值,然后根据取中间元素构建根节点,依次进行递归迭代左右结点即可
        def helper(vals):
            if vals:
                mid = len(vals) // 2
                root = TreeNode(vals[mid])
                root.left = helper(vals[:mid])
                root.right = helper(vals[mid+1:])
                return root
        if not head:
            return
        # 获取所有的元素值
        vals = []
        while head:
            vals.append(head.val)
            head = head.next
        return helper(vals)

上述解决问题的思路可以说一种取巧的思路,那么我们能够直接操作单链表来查询中间结点呢?答案是,当然可以。为了直接操作单链表来获取中间结点,我们首先要明确怎么来进行遍历查找。

既然是中间结点,那么就是整个单链表的中间元素,我们如果知道整个链表长度,然后再遍历一次链表取中间长度的岂不是就可以了吗?但是这样势必会花费更多的时间,从而导致效率低下。那我们能否将这遍历的操作放在同一个过程中呢?这样我们就可以一次遍历完成了。因此,我们使用两个指针(也就是双指针法)slow、fast,让slow每次走一步,fast走两步,那么当fast走到尾部的时候,slow刚好走到中间位置。注意:由于后续需要再递归求解左右子树,我们需要将单链表从中间位置断开,这时我们需要一个pre指针来记录slow的前一个位置。具体实现代码如下:

Python版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

    def findMiddle(self, head):

        # pre指针用来将左边从中间结点断开
        prev = None
        slow = head
        fast = head

        # 迭代执行直到尾指针到达链表结尾
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        # 从中间结点进行断开
        if prev:
            prev.next = None

        return slow

    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: 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

Java版本

/**
 * 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;
        ListNode mid = this.findMiddle(head);
        TreeNode node = new TreeNode(mid.val);
        if(head == mid)
            return node;
        node.left = this.sortedListToBST(head);
        node.right = this.sortedListToBST(mid.next);
        return node;
    }
    public ListNode findMiddle(ListNode node){
        if(node == null)
            return null;
        ListNode pre = null;
        ListNode slow = node;
        ListNode fast = node;
        while(fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        if(pre != null)
            pre.next = null;
        return slow;
    }
}

本文分享自微信公众号 - 机器学习与推荐算法(ML_RSer)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【一分钟知识】七种损失函数

    0-1, Hinge, Logistic, Cross Entropy, Square, Absolute, Huber

    张小磊
  • 基于图卷积的价格感知推荐

    Paper:Price-aware Recommendation with Graph Convolutional Networks

    张小磊
  • SIGIR2020 | 基于GCN的鲁棒推荐系统研究

    近年来,推荐系统已成为所有电子商务平台中必不可少的组件。然而,推荐系统的评分数据通常来自开放平台,而开放平台可能会存在一群恶意用户故意插入虚假反馈,以使推荐系统...

    张小磊
  • leetcode-83-Remove Duplicates from Sorted List

    chenjx85
  • Leetcode 86. Partition List

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Python 中 os.path 模块的

      https://docs.python.org/3/library/os.path.html

    py3study
  • 漏洞预警:CVE-2019-11043/PHP-FPM(RCE)

    2019年9月26日,PHP官方发布漏洞通告称nginx + php-fpm服务器在部分错误配置下存在远程代码执行漏洞。2019年10月22日,外籍白帽子And...

    Aran
  • Failed to connect to raw.githubusercontent.com port 443 解决方案

    由于某些你懂的因素,导致GitHub的raw.githubusercontent.com域名解析被污染了。

    Theone67
  • 【NPM库】- 0x05 - 文件、路径操作

    1.3. path.dirname、path.join、path.resolve、path.relative

    WEBJ2EE
  • 护网杯easy laravel ——Web菜鸡的详细复盘学习

    复现让我发现了很多读wp以为懂了动手做的时候却想不通的漏掉的知识点(还是太菜orz),也让我对这道题解题逻辑更加理解。所以不要怂,就是干23333!

    安恒网络空间安全讲武堂

扫码关注云+社区

领取腾讯云代金券