leetcode — convert-sorted-list-to-binary-search-tree

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<Character> chs) {

        if (root == null) {

            chs.add('#');

            return;

        }

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

        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<Character> chs = new ArrayList<Character>();

        TreeNode root = convertSortedList.convert(convertSortedList.createList(arr));

        convertSortedList.binarySearchTreeToArray(root, chs);

        System.out.println(Arrays.toString(chs.toArray(new Character[chs.size()])));

    }

}
巴特西

leetcode — convert-sorted-list-to-binary-search-tree

最新文章

热门文章
