package mrzhang.leecode;

/**
 * @author zhangnianlei
 * @date 2020/7/8
 *
 * 109. 有序链表转换二叉搜索树
 */
public class Solution109function3 {

	private ListNode head;

	public static void main(String[] args) {
		int[] nums = {-10,-3,0,5,9, 13};
		// 构建一个ListNode
		ListNode listNode = ListNode.getListNode(nums);
		Solution109function3 solution109 = new Solution109function3();
		TreeNode root = solution109.sortedListToBST(listNode);
		TreeNode.prePrint(root);
	}

	/**
	 * @description leetcode 109 方法三 逆用中序遍历的思想：中序遍历二叉搜索树得到一个升序数列，那么反过来，使用此法将一个升序的数列构建成一个二叉搜索树
	 * @author zhangnianlei
	 * @date 2020/7/9
	 * @exception
	 * @param: node
	 * @return: mrzhang.leecode.TreeNode
	 * @modifier
	 */
	private TreeNode sortedListToBST(ListNode node) {
		// 计算listNode的长度
		int size = countListNodeSize(node);
		// 使用全局的ListNode变量协助
		head = node;
		// 构建二叉搜索树
		return convertListToBST(0, size - 1);
	}

	/**
	 * @description 计算listNode的长度
	 * @author zhangnianlei
	 * @date 2020/7/11
	 * @exception
	 * @param: left
	 * @param: right
	 * @return: mrzhang.leecode.TreeNode
	 * @modifier
	 */
	private TreeNode convertListToBST(int left, int right) {
		if (right < left) return null;
		int mid = (right + left) / 2;
		TreeNode leftNode = convertListToBST(left, mid - 1);
		TreeNode result = new TreeNode(head.val);
		result.left = leftNode;
		head = head.next;
		result.right = convertListToBST(mid + 1, right);
		return result;
	}

	/**
	 * @description 计算listNode的长度
	 * @author zhangnianlei
	 * @date 2020/7/11
	 * @exception
	 * @param: head
	 * @return: int
	 * @modifier
	 */
	private int countListNodeSize(ListNode head) {
		if (head == null) return 0;
		int sum = 0;
		ListNode p = head;
		while (p != null) {
			sum += 1;
			p = p.next;
		}
		return sum;
	}

}