package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 109. 有序链表转换二叉搜索树
 * 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
 *
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
 *
 *
 * @author :Tang
 * @date 2021/7/17
 */
public class SortedListToBST {


    /**
     * 先确定根节点 链表中间位置
     * 把链表分成两个链表 继续确定根节点
     *
     *
     * @param head
     * @return
     */
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        return specifyMidNode(list);
    }

    private TreeNode specifyMidNode(List<Integer> list){
        if(list == null || list.size() == 0){
            return null;
        }
        int mid = list.size() / 2;
        TreeNode node = new TreeNode(list.get(mid));
        List<Integer> list0 = list.subList(0, mid);
        List<Integer> list1 = list.subList(mid+1, list.size());
        TreeNode left = specifyMidNode(list0);
        TreeNode right = specifyMidNode(list1);
        node.left = left;
        node.right = right;
        return node;
    }


    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        listNode.next = listNode2;
        new SortedListToBST().sortedListToBST(listNode);

    }



}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

}