[LintCode/LeetCode] Convert Sorted List to Balance

Michael_Ding 發布于2019-08-14 15:32 / 2360人閱讀

摘要：當鏈表為空時，中出現大于，返回。然后計算中點，以為界分別遞歸構建左右子樹。順序是，左子樹根結點右子樹。由于根節點是直接取構建，當前的已經被取用。所以在下一次遞歸構建右子樹之前，要讓指向。最后將和左右子樹相連，返回。

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;
    }
}

GPU云服務器云服務器 Balance Sorted convert sorted-array

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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