將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。

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

示例:

給定有序數組: [-10,-3,0,5,9],一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹：0/ \-3 9/ /-10 5

?

?

思路1： 遍歷鏈表，獲得鏈表長度，找到鏈表中間的值，形成根結點，根據left,right ，遞歸尋找結點的左子樹和右子樹。 因為每次遞歸都要遍歷鏈表，時間復雜度非常高， /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution {public TreeNode sortedListToBST(ListNode head) {if(head==null)return null;ListNode l1=head,l2=head;int count=0;while(l1!=null){l1=l1.next;count++; //得到鏈表的長度 }// for(int i=0;i<count/2;i++){// l2=l2.next; //得到鏈表的中點// }return buildBST(head,0,count-1);}public TreeNode buildBST(ListNode head,int l,int r){if(l>r)return null;int mid=(l+r)/2;ListNode tem=head;for(int i=0;i<mid;i++)tem=tem.next; //每次遞歸都要遍歷鏈表TreeNode root=new TreeNode(tem.val);root.left=buildBST(head,l,mid-1);root.right=buildBST(head,mid+1,r);return root;} }

?

思路2：先轉化為數組，再轉化為有序數組轉換二叉探索樹。

參考：

leetcode- 將有序數組轉換為二叉搜索樹(java)

?

class Solution {public TreeNode sortedListToBST(ListNode head) {if(head==null)return null;int count=0;ListNode l1=head;while(l1!=null){l1=l1.next;count++;}int[] nums=new int[count];for(int i=0;i<count;i++){nums[i]=head.val;head=head.next; //轉化為數組 }return buildBST(nums,0,count-1); //將排序數組轉為二叉探索樹 }public TreeNode buildBST(int[] nums,int l,int r){if(l>r)return null; int mid=(l+r)/2;TreeNode root=new TreeNode(nums[mid]);root.left=buildBST(nums,l,mid-1);root.right=buildBST(nums,mid+1,r);return root;} }

?新的思路：

使用快慢指針解決，慢指針遍歷之后處于鏈表中間位置，slow位置就是根結點，slow->next就是二叉樹的右子樹， 左邊就是左子樹。? 要將左子樹和右子樹之間的鏈表斷裂last.next=null? ,fast=slow.next;? 左右子樹都不包含根結點 class Solution {public TreeNode sortedListToBST(ListNode head) { //注意若子樹只有兩個節點，只需以首節點為根構造右子節點為其后節點的子樹if(head==null)return null;if(head.next==null)return new TreeNode(head.val);ListNode fast=head,slow=head,last=slow;while(fast.next!=null&&fast.next.next!=null){last=slow; //這里執行到最后一步的時候，last只比slow慢一個指針。slow=slow.next;fast=fast.next.next; }TreeNode root=new TreeNode(slow.val);fast=slow.next;//fast部分的鏈表轉化為右子樹if(slow!=last){ last.next=null;root.left=sortedListToBST(head);}root.right=sortedListToBST(fast);return root;} }

?

轉載于:https://www.cnblogs.com/patatoforsyj/p/10062762.html

總結

以上是生活随笔為你收集整理的有序链表转换二叉搜索树（LeetCode）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。