本文共 1227 字，大约阅读时间需要 4 分钟。

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

思路：用快慢结点的思路来求出链表的中间结点，使其生成根节点

package com.lcz.leetcode;/** * 有序链表转换二叉搜索树 * @author LvChaoZhang * */public class Leetcode109 {
   	class ListNode{
   		int val;		ListNode next;		ListNode(){
   					}		ListNode(int val){
   			this.val = val;		}		ListNode(int val,ListNode next){
   			this.val = val;			this.next = next;		}	}		class TreeNode{
   		int val;		TreeNode left;		TreeNode right;		TreeNode(){
   					}		TreeNode(int val){
   			this.val = val;		}		TreeNode(int val,TreeNode left,TreeNode right){
   			this.val = val;			this.left = left;			this.right = right;		}	}		public TreeNode sortedListToBST(ListNode head) {
   		return dfs(head,null);			}		private TreeNode dfs(ListNode left,ListNode right) {
   		// 遍历终止条件		if(left==right) {
   			return null;		}		ListNode mid = getMedian(left,right);		TreeNode root = new TreeNode(mid.val);		root.left = dfs(left,mid);		root.right = dfs(mid.next,right);		return root;	}		private ListNode getMedian(ListNode left,ListNode right) {
   		ListNode fast = left;		ListNode slow  = left;		while(fast!=right&&fast.next!=right) {
   			fast = fast.next.next;			slow = slow.next;		}		return slow;	}}

转载地址：http://pwwdf.baihongyu.com/