「力扣」第 109 题:有序链表转换二叉搜索树


「力扣」第 109 题:有序链表转换二叉搜索树

题解地址:分治法(Python 代码、Java 代码)

说明:文本首发在力扣的题解版块,更新也会在第 1 时间在上面的网站中更新,这篇文章只是上面的文章的一个快照,您可以点击上面的链接看到其他网友对本文的评论。

传送门:109. 有序链表转换二叉搜索树

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

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

示例:

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

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

  0
 / \

-3 9
/ /
-10 5

分治法(Python 代码、Java 代码)

思路分析

思路其实官方题解已经写得非常清楚了,建议看看其中的动画,生动形象。

在这里主要想说二叉树的很多问题基本上都可以通过“分而治之”的策略完成。这里首先找到单链表的中间结点,然后递归构造左子树和右子树。还有一种做法是把单链表变成有序数组,这就是 「力扣」第 108 题:将有序数组转换为二叉搜索树

编码的细节已经体现在代码注释中。

参考代码

Python 代码:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        # 特判:当结点为空,或者单结点的时候的简单逻辑
        if head is None:
            return None

        if head.next is None:
            return TreeNode(head.val)

        # 设置 pre 指针是为了切断单链表 mid 的前半部分
        pre = None
        slow = head
        fast = head

        # 如果写 while fast and fast.next: 后面的代码稍有不同
        while fast.next and fast.next.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next

        # 此时 slow 结点就位于链表的中部,
        # 它的值就作为 BST 的根结点返回
        root = TreeNode(slow.val)

        # 因为要传入下一个递归方法,所以得先保存索引
        new_head = slow.next
        slow.next = None

        # 当链表只有 2 个结点的时候,pre 指针此时为 None,不用递归构造左子树
        if pre:
            pre.next = None
            root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(new_head)
        return root

Java 代码:

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    public TreeNode sortedListToBST(ListNode head) {
        // 特判:当结点为空,或者单结点的时候的简单逻辑
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }

        // 设置 pre 指针是为了切断单链表 mid 的前半部分
        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;

        // 如果写 while fast and fast.next: 后面的代码稍有不同
        while (fast.next != null && fast.next.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        // 此时 slow 结点就位于链表的中部,
        // 它的值就作为 BST 的根结点返回
        TreeNode root = new TreeNode(slow.val);
        // 因为要传入下一个递归方法,所以得先保存索引
        ListNode newHead = slow.next;
        slow.next = null;

        // 当链表只有 2 个结点的时候,pre 指针此时为 null,不用递归构造左子树
        if(pre != null){
            pre.next = null;
            root.left = sortedListToBST(head);
        }
        root.right = sortedListToBST(newHead);
        return root;
    }
}

文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 240 题:搜索二维矩阵 II 「力扣」第 240 题:搜索二维矩阵 II
「力扣」第 240 题:搜索二维矩阵 II题解地址:排除法(不是什么新方法,就是你们最常看到的那个解法,从右下角、左上角开始)(Python 代码、Java 代码)。 说明:文本首发在力扣的题解版块,更新也会在第 1 时间在上面的网站中更新
下一篇 
「力扣」第 106 题:从中序与后序遍历序列构造二叉树 「力扣」第 106 题:从中序与后序遍历序列构造二叉树
「力扣」第 106 题:从中序与后序遍历序列构造二叉树题解地址:分治法(Python、Java)。 说明:文本首发在力扣的题解版块,更新也会在第 1 时间在上面的网站中更新,这篇文章只是上面的文章的一个快照,您可以点击上面的链接看到其他网友
  目录