java如何將有序鏈表轉(zhuǎn)換二叉搜索樹(shù)

這篇“java如何將有序鏈表轉(zhuǎn)換二叉搜索樹(shù)”文章，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要參考一下，對(duì)于“java如何將有序鏈表轉(zhuǎn)換二叉搜索樹(shù)”，小編整理了以下知識(shí)點(diǎn)，請(qǐng)大家跟著小編的步伐一步一步的慢慢理解，接下來(lái)就讓我們進(jìn)入主題吧。

給定一個(gè)單鏈表，其中的元素按升序排序，將其轉(zhuǎn)換為高度平衡的二叉搜索樹(shù)。

本題中，一個(gè)高度平衡二叉樹(shù)是指一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1。

示例:

給定的有序鏈表： [-10, -3, 0, 5, 9],

一個(gè)可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面這個(gè)高度平衡二叉搜索樹(shù)：

      0

     /   \

   -3     9

   /        /

 -10    5

答案：

 1public TreeNode sortedListToBST1(ListNode head) {
 2    if (head == null) return null;
 3    return toBST(head, null);
 4}
 5
 6public TreeNode toBST(ListNode head, ListNode tail) {
 7    ListNode slow = head;
 8    ListNode fast = head;
 9    if (head == tail) return null;
10
11    while (fast != tail && fast.next != tail) {
12        fast = fast.next.next;
13        slow = slow.next;
14    }
15    TreeNode thead = new TreeNode(slow.val);
16    thead.left = toBST(head, slow);
17    thead.right = toBST(slow.next, tail);
18    return thead;
19}

解析：

這題比較簡(jiǎn)單，因?yàn)槲覀円阎湵硎怯行虻?，要想轉(zhuǎn)化為高度平衡的二叉樹(shù)，我們只需要用排序鏈表的中間節(jié)點(diǎn)當(dāng)做二叉樹(shù)的根節(jié)點(diǎn)，前面部分作為二叉樹(shù)的左子樹(shù)，后面部分作為二叉樹(shù)的右子樹(shù)，然后在以同樣的方式分別遞歸左右子樹(shù)即可。再來(lái)?yè)Q種寫(xiě)法

 1public TreeNode sortedListToBST(ListNode head) {
 2    if (head == null)
 3        return null;
 4    if (head.next == null)
 5        return new TreeNode(head.val);
 6    ListNode slow = head, pre = null, fast = head;
 7    while (fast != null && fast.next != null) {
 8        pre = slow;
 9        slow = slow.next;
10        fast = fast.next.next;
11    }
12    pre.next = null;
13    TreeNode n = new TreeNode(slow.val);
14    n.left = sortedListToBST(head);
15    n.right = sortedListToBST(slow.next);
16    return n;
17}

其實(shí)思路還都是一樣的，其中第12行是相當(dāng)于把鏈表兩邊的前后兩部分?jǐn)嚅_(kāi)。slow成為當(dāng)前節(jié)點(diǎn)，slow的前部分變成當(dāng)前節(jié)點(diǎn)的左子樹(shù)，slow的后半部分變成當(dāng)前節(jié)點(diǎn)的右子樹(shù)。

Java可以用來(lái)干什么

Java主要應(yīng)用于：1. web開(kāi)發(fā)；2. Android開(kāi)發(fā)；3. 客戶(hù)端開(kāi)發(fā)；4. 網(wǎng)頁(yè)開(kāi)發(fā)；5. 企業(yè)級(jí)應(yīng)用開(kāi)發(fā)；6. Java大數(shù)據(jù)開(kāi)發(fā)；7.游戲開(kāi)發(fā)等。

以上是“java如何將有序鏈表轉(zhuǎn)換二叉搜索樹(shù)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！