溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇“java如何將有序鏈表轉換二叉搜索樹”文章，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要參考一下，對于“java如何將有序鏈表轉換二叉搜索樹”，小編整理了以下知識點，請大家跟著小編的步伐一步一步的慢慢理解，接下來就讓我們進入主題吧。
給定一個單鏈表，其中的元素按升序排序，將其轉換為高度平衡的二叉搜索樹。
本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 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主要應用于：1. web開發；2. Android開發；3. 客戶端開發；4. 網頁開發；5. 企業級應用開發；6. Java大數據開發；7.游戲開發等。
以上是“java如何將有序鏈表轉換二叉搜索樹”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
