[LintCode/LeetCode] Convert Sorted List to Balance

Michael_Ding 发布于2019-08-14 15:32 / 2113人阅读

摘要：当链表为空时，中出现大于，返回。然后计算中点，以为界分别递归构建左右子树。顺序是，左子树根结点右子树。由于根节点是直接取构建，当前的已经被取用。所以在下一次递归构建右子树之前，要让指向。最后将和左右子树相连，返回。

Problem

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Example

               2
1->2->3  =>   / 
             1   3

Note

用递归的方法来做，首先新建cur结点来复制head结点，然后计算链表head的长度，调用helper(start, end)函数建立平衡BST。
当链表为空时，helper()中出现start大于end，返回null。然后计算中点mid，以mid为界分别递归构建左右子树。顺序是，左子树-->根结点-->右子树。由于根节点root是直接取cur.val构建，当前的cur已经被取用。所以在下一次递归构建右子树之前，要让cur指向cur.next。最后将root和左右子树相连，返回root。

Solution

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

私有云云服务器 Balance Sorted convert sorted-array

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65831.html

[LintCode/LeetCode] Merge Two Sorted Lists

摘要：先考虑和有无空集，有则返回另一个。新建链表，指针将和较小的放在链表顶端，然后向后遍历，直到或之一为空。再将非空的链表放在后面。 Problem Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splici...

dockerclub 2019-08-14 15:22 评论0 收藏0
[LintCode/LeetCode] Merge Sorted Array

Problem Given two sorted integer arrays A and B, merge B into A as one sorted array. Notice You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements ...

summerpxy 2019-08-14 15:41 评论0 收藏0
[LintCode/LeetCode] Find Minimum in Rotated Sorted

摘要：排序数组中找最小值或最大值的题目，很明显可以使用二分法。因此，只判断终点和中点元素的大小关系即可。这里有一种情况是上述后三个，中点值和末位相等。此时，两边同时递归，并返回两边递归值的较小值。当首位和末位重合，说明已夹逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

cgh1999520 2019-08-14 15:22 评论0 收藏0
[LintCode/LeetCode] Search in Rotated Sorted Arra

摘要：找中点若起点小于中点，说明左半段没有旋转，否则说明右半段没有旋转。在左右半段分别进行二分法的操作。只判断有无，就容易了。还是用二分法优化 Search in Rotated Sorted Array Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 ...

U2FsdGVkX1x 2019-08-14 15:41 评论0 收藏0
[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立两个堆，一个堆就是本身，也就是一个最小堆另一个要写一个，使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里，更大的数放在最小堆，较小的数放在最大堆。同时，确保最大堆的比最小堆大，才能从最大堆的顶端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 评论0 收藏0