leetcode109有序链表转换二叉搜索树(JAVA实现)(前序遍历二叉树)
解答:递归前序遍历
/**
* 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 ListNode findMiddleElement(ListNode head)
{
ListNode prevPtr=null;
ListNode slowPtr=head;
ListNode fastPtr=head;
while(fastPtr!=null&&fastPtr.next!=null)
{
prevPtr=slowPtr;
slowPtr=slowPtr.next;
fastPtr=fastPtr.next.next;
}
if(prevPtr!=null)//截断链表
{
prevPtr.next=null;
}
return slowPtr;
}
public TreeNode sortedListToBST(ListNode head) {
if(head==null)
{
return null;
}
ListNode mid=this.findMiddleElement(head);//用同一个class里面的方法用this
TreeNode node=new TreeNode(mid.val);
if(head==mid)
return node;
node.left=this.sortedListToBST(head);//是sort不是find
node.right=this.sortedListToBST(mid.next);
return node;
}
}