给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
链接:https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
平衡链表有很多种
注意一点,二叉排序树中序遍历是从小到大的。
public TreeNode sortedListToBST(ListNode head) {
if(head==null)
return null;
ListNode cur=head;
ArrayList<Integer> arr= new ArrayList<>();
while (cur!=null)
{
arr.add(cur.val);
cur=cur.next;
}
return RecurBuid(0,arr.size()-1,arr);
}
public TreeNode RecurBuid(int start,int end,ArrayList<Integer> arr)
{
if(start>end)
return null;
int mid=start+((end-start)>>1);
TreeNode root=new TreeNode(arr.get(mid));
root.left=RecurBuid(start,mid-1,arr);
root.right=RecurBuid(mid+1,end,arr);
return root;
}