import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * Source : https://oj.leetcode.com/problems/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. */public class ConvertSortedList {    /**     * 将一个有序链表转化为一棵AVL树     * 可以先把单向链表转化为有序数组，然后将数组转化为AVL树     * 或者使用双指针，快指针每次移动两个位置，慢指针每次移动一个位置，这样就能找到中间的节点     *     * 还有一种方法：     * 找到链表总个数total，一次递归如下：     * 递归查找左子树，每次递归的时候将head指向下一个节点     * 左子树递归完成之后，head指向了mid节点     * 构造root节点，当前head指向的就是mid节点，也就是root节点     * 递归构造右子树     * 构造根节点，并返回     *     * @param head     * @return     */    public TreeNode convert (ListNode head) {        ListNode node = head;        int total = 0;        while (node != null) {            total++;            node = node.next;        }        return convert(new HeadHolder(head), 0, total-1);    }    /**     * 因为每次递归需要改变head的值，所以使用一个HeadHolder指向head，每次修改headHolder的指向     *     * @param head     * @param left     * @param right     * @return     */    public TreeNode convert (HeadHolder head, int left, int right) {        if (left > right) {            return null;        }        int mid = (left + right) / 2;        TreeNode leftChild = convert(head, left, mid-1);        // 上面递归完成之后，head指向了mid位置的节点        TreeNode root = new TreeNode(head.head.value);        // head的下一个节点就是右子树的第一个节点        head.head = head.head.next;        TreeNode rightChild = convert(head, mid+1, right);        root.leftChild = leftChild;        root.rightChild = rightChild;        return root;    }    private class HeadHolder {        ListNode head;        public HeadHolder(ListNode head) {            this.head = head;        }    }    public ListNode createList (int[] arr) {        if (arr.length == 0) {            return null;        }        ListNode head = new ListNode();        head.value = arr[0];        ListNode pointer = head;        for (int i = 1; i < arr.length; i++) {            ListNode node = new ListNode();            node.value = arr[i];            pointer.next = node;            pointer = pointer.next;        }        return head;    }    public void binarySearchTreeToArray (TreeNode root, List
    
      chs) {        if (root == null) {            chs.add('#');            return;        }        List
     
       list = new ArrayList
      
       ();        int head = 0;        int tail = 0;        list.add(root);        chs.add((char) (root.value + '0'));        tail ++;        TreeNode temp = null;        while (head < tail) {            temp = list.get(head);            if (temp.leftChild != null) {                list.add(temp.leftChild);                chs.add((char) (temp.leftChild.value + '0'));                tail ++;            } else {                chs.add('#');            }            if (temp.rightChild != null) {                list.add(temp.rightChild);                chs.add((char)(temp.rightChild.value + '0'));                tail ++;            } else {                chs.add('#');            }            head ++;        }        //去除最后不必要的        for (int i = chs.size()-1; i > 0; i--) {            if (chs.get(i) != '#') {                break;            }            chs.remove(i);        }    }    private class TreeNode {        TreeNode leftChild;        TreeNode rightChild;        int value;        public TreeNode(int value) {            this.value = value;        }        public TreeNode() {        }    }    private class ListNode {        ListNode next;        int value;        public ListNode(int value) {            this.value = value;        }        public ListNode() {        }    }    public static void main(String[] args) {        ConvertSortedList convertSortedList = new ConvertSortedList();        int[] arr = new int[]{1,2,3,4,5,6};        List
       
         chs = new ArrayList
        
         ();        TreeNode root = convertSortedList.convert(convertSortedList.createList(arr));        convertSortedList.binarySearchTreeToArray(root, chs);        System.out.println(Arrays.toString(chs.toArray(new Character[chs.size()])));    }}