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

目前創(chuàng)新互聯(lián)已為1000+的企業(yè)提供了網(wǎng)站建設(shè)、域名、雅安服務(wù)器托管、網(wǎng)站改版維護(hù)、企業(yè)網(wǎng)站設(shè)計、蒙山網(wǎng)站維護(hù)等服務(wù)，公司將堅持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

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

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

示例:

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

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

      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}

解析：

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

 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)嚅_。slow成為當(dāng)前節(jié)點(diǎn)，slow的前部分變成當(dāng)前節(jié)點(diǎn)的左子樹，slow的后半部分變成當(dāng)前節(jié)點(diǎn)的右子樹。

Java可以用來干什么

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

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

當(dāng)前標(biāo)題：java如何將有序鏈表轉(zhuǎn)換二叉搜索樹
文章源于：http://jinyejixie.com/article28/podpcp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營銷、ChatGPT、網(wǎng)頁設(shè)計公司、Google、網(wǎng)站改版、品牌網(wǎng)站設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)