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

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

示例:

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

/*** 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) {return build(head,null);}public TreeNode build(ListNode start,ListNode end){if(start==end){return null;}ListNode oneStep=start;ListNode twoStep=start;while(twoStep!=end&&twoStep.next!=end){oneStep=oneStep.next;twoStep=twoStep.next.next;}TreeNode root= new TreeNode(oneStep.val);root.left=build(start,oneStep);root.right=build(oneStep.next,end);return root;} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/JAYPARK/p/10539411.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。