本文主要是介绍leetcode 109. Convert Sorted List to Binary Search Tree 源代码加详细思路和注释，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Subscribe to see which companies asked this question
题目分析：将排好序的链表转换成平衡二叉树。我们想一下怎么将排好序的数组转换成平衡二叉树，首先找到根节点，之后递归的构建左右子树。那么转换为链表，怎么找到根节点，想到常用的链表思路：快慢指针，快速找到中间位置的根节点。
public class Solution {public TreeNode sortedListToBST(ListNode head) {if(head==null) return null;if(head.next==null) return new TreeNode(head.val);return toBST(head,null);}public TreeNode toBST(ListNode head,ListNode tail){if(head==tail) return null; //head是起始节点，tail是终止结点的下一个结点ListNode slow=head;ListNode fast=head;while(fast!=tail&&fast.next!=tail)//通过快慢指针快速找到根节点{fast=fast.next.next;slow=slow.next;}TreeNode res=new TreeNode(slow.val);res.left=toBST(head,slow);//递归的构建左子树，右子树res.right=toBST(slow.next,tail);return res;}
}
这篇关于leetcode 109. Convert Sorted List to Binary Search Tree 源代码加详细思路和注释的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
