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

目前創新互聯已為1000+的企業提供了網站建設、域名、雅安服務器托管、網站改版維護、企業網站設計、蒙山網站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協力一起成長，共同發展。

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

本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 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}

解析：

這題比較簡單，因為我們已知鏈表是有序的，要想轉化為高度平衡的二叉樹，我們只需要用排序鏈表的中間節點當做二叉樹的根節點，前面部分作為二叉樹的左子樹，后面部分作為二叉樹的右子樹，然后在以同樣的方式分別遞歸左右子樹即可。再來換種寫法

 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}

其實思路還都是一樣的，其中第12行是相當于把鏈表兩邊的前后兩部分斷開。slow成為當前節點，slow的前部分變成當前節點的左子樹，slow的后半部分變成當前節點的右子樹。

Java可以用來干什么

Java主要應用于：1. web開發；2. Android開發；3. 客戶端開發；4. 網頁開發；5. 企業級應用開發；6. Java大數據開發；7.游戲開發等。

以上是“java如何將有序鏈表轉換二叉搜索樹”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注創新互聯行業資訊頻道！

當前標題：java如何將有序鏈表轉換二叉搜索樹
文章源于：http://vcdvsql.cn/article28/podpcp.html

成都網站建設公司_創新互聯，為您提供網站營銷、ChatGPT、網頁設計公司、Google、網站改版、品牌網站設計

廣告

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