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

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

示例:

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

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

      0
     / \
   -3   9
   /   /
 -10  5

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

解法1

二叉搜索树(BST)是一种特殊的二叉树,他满足左子树的全部元素都小于根节点,右子树的全部元素都大于根节点。题目另外要求生成的平衡的BST,意味着在上面的基础上又添加了新条件:左右子树高度差的绝对值不超过1。

首先给定的链表是有序的,加上BST本身的特性会使我们联想到二分查找的思想。根据有序列表构建BST我们可以使用类似于二分查找的思路,用中心元素将链表划分为两部分,左半部分都小于中心元素、右半部分都大于中心元素。

采用链表作为数据结构,不容易实现随机访问。为了能够快速的获取中心元素,我们首先将链表转换为数组。我们取数组长度的一半作为中心元素的索引。中心元素作为二叉树的根节点,将左半部分与右半部分以相同的方式处理继续构建左子树与右子树。直到左半部分或右半部分没有元素时,构建过程停止。

下面以题目以“[-10, -3, 0, 5, 9]”为例,构建BST。下面的图片给出了两颗BST,他们都是合法的,但我们的处理逻辑仅能够产生左边的形态。

图1 两颗合法的BST

我们列举BST的构建过程来说明,为什么我们的逻辑只能够产生左边的形态。首先,说明下我们采用的边界都是左闭右开的形式。arr=[-10, -3, 0, 5, 9]。|arr|=5, mid = (0+5)/2 = 2,取arr[2]=0作为中间元素,左半部分为[-10, -3],右半部分为[5, 9]。我们继续利用左半部分构建根节点0的左子树。计算|[-10, -3]| = 2,mid = (0+2)/2 = 1,取arr[1]=-3作为根节点。我们可以看到,因为左子树仅有两个元素,按照我们mid=(左边界索引+右边界索引)/2的处理方式会将第二个元素-3作为子树的根节点,而不是-10作为根节点。

我们来分析下,为什么这么做能够构建出平衡的BST。很容易想到按照上面的方法一定能够构建出BST,也就是满足左子树的全部元素都小于根节点,右子树的全部元素都大于根节点的性质。因为我们数组是被排序的,我们计算出中间元素根节点。利用中间元素将数组划分为两部分,左右两部分分别构建左右子树。数组被划分成两部分,这两部分同样满足左边都小于中间元素,右边都大于中间元素的性质,这与BST的性质正好一致。

这么做为什么能构建出平衡的BST比较费解。我们举例分析,如果数组arr的长度为奇数,例如7。那么中间元素arr[3]作为中间元素,左边还剩下arr[0]、arr[1]、arr[2]三个元素,右边还剩下arr[4]、arr[5]、arr[6]三个元素。这么做左右子树的节点数量是相同的。他们又可以继续被划分,继续构建子树。若数组arr的长度为偶数,例如6。那么中间元素arr[3]作为中间元素,左边剩下arr[0]、arr[1]、arr[2]三个元素,右边剩下arr[4]、arr[5]两个元素。两个元素构建子树的高度之差为1。也就是说无论数组arr的长度为多少,最后构建子树的左右高度之差都会是0或者1。下面是全部代码。

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> arr = new ArrayList<>();

        while (head != null) {
            arr.add(head.val);
            head = head.next;
        }

        return sortedListToBST(arr, 0, arr.size());

    }

    public TreeNode sortedListToBST(List<Integer> arr, int left, int right) {
        if (left >= right)
            return null;
        if (right - left == 1)
            return new TreeNode(arr.get(left));
        // 不采用 (left + right) / 2以防止溢出
        int mid = left + (right - left) / 2;
        TreeNode treeNode = new TreeNode(arr.get(mid));

        treeNode.left = sortedListToBST(arr, left, mid);
        treeNode.right = sortedListToBST(arr, mid + 1, right);

        return treeNode;
    }
}
pwrliang Algorithms, Tree , , ,

Leave a Reply

Your email address will not be published. Required fields are marked *