[leetcode]Convert SortedList To Binary Search Tree - java 递归

递归构造二叉查找树

 

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; next = null; }

 * }

 */

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public TreeNode sortedListToBST(ListNode head) {

        if(head==null){

            return null;

        }

        List<Integer> list = new ArrayList<Integer>();

        ListNode p = head;

        while (p!=null){

            list.add(p.val);

            p = p.next;

        }

        TreeNode root = convert(list, 0, list.size()-1);

        return root;

    }



    private TreeNode convert(List<Integer> list, int start, int end){

        if(start>end){

            return null;

        }

        int mid = start + (end-start)/2;

        TreeNode parent = new TreeNode(list.get(mid));

        TreeNode left = convert(list, start, mid-1);

        parent.left=left;

        TreeNode right = convert(list, mid+1, end);

        parent.right=right;

        return parent;

    }

}