資訊專欄INFORMATION COLUMN
摘要：當(dāng)鏈表為空時(shí)，中出現(xiàn)大于，返回。然后計(jì)算中點(diǎn)，以為界分別遞歸構(gòu)建左右子樹。順序是，左子樹根結(jié)點(diǎn)右子樹。由于根節(jié)點(diǎn)是直接取構(gòu)建，當(dāng)前的已經(jīng)被取用。所以在下一次遞歸構(gòu)建右子樹之前，要讓指向。最后將和左右子樹相連，返回。
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結(jié)點(diǎn)來復(fù)制head結(jié)點(diǎn)，然后計(jì)算鏈表head的長度，調(diào)用helper(start, end)函數(shù)建立平衡BST。
當(dāng)鏈表為空時(shí)，helper()中出現(xiàn)start大于end，返回null。然后計(jì)算中點(diǎn)mid，以mid為界分別遞歸構(gòu)建左右子樹。順序是，左子樹-->根結(jié)點(diǎn)-->右子樹。由于根節(jié)點(diǎn)root是直接取cur.val構(gòu)建，當(dāng)前的cur已經(jīng)被取用。所以在下一次遞歸構(gòu)建右子樹之前，要讓cur指向cur.next。最后將root和左右子樹相連，返回root。
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/65831.html
摘要：先考慮和有無空集，有則返回另一個(gè)。新建鏈表，指針將和較小的放在鏈表頂端，然后向后遍歷，直到或之一為空。再將非空的鏈表放在后面。 Problem Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splici...
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 ...
摘要：排序數(shù)組中找最小值或最大值的題目，很明顯可以使用二分法。因此，只判斷終點(diǎn)和中點(diǎn)元素的大小關(guān)系即可。這里有一種情況是上述后三個(gè)，中點(diǎn)值和末位相等。此時(shí)，兩邊同時(shí)遞歸，并返回兩邊遞歸值的較小值。當(dāng)首位和末位重合，說明已夾逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...
摘要：找中點(diǎn)若起點(diǎn)小于中點(diǎn)，說明左半段沒有旋轉(zhuǎn)，否則說明右半段沒有旋轉(zhuǎn)。在左右半段分別進(jìn)行二分法的操作。只判斷有無，就容易了。還是用二分法優(yōu)化 Search in Rotated Sorted Array Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 ...
摘要：建立兩個(gè)堆，一個(gè)堆就是本身，也就是一個(gè)最小堆另一個(gè)要寫一個(gè)，使之成為一個(gè)最大堆。我們把遍歷過的數(shù)組元素對(duì)半分到兩個(gè)堆里，更大的數(shù)放在最小堆，較小的數(shù)放在最大堆。同時(shí)，確保最大堆的比最小堆大，才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...
閱讀 3458·2021-11-24 09:38
閱讀 1443·2021-11-22 15:08
閱讀 1542·2021-09-29 09:35
閱讀 552·2021-09-02 15:11
閱讀 1362·2019-08-30 12:55
閱讀 439·2019-08-29 17:16
閱讀 555·2019-08-29 11:30
閱讀 475·2019-08-26 13:23
