昨天的层次遍历二叉树，本质就是前序遍历二叉树。
今天又学习了两道中序遍历的题目。
第二题相比第一题难度有所上升，不过本质完全相同。

第一题

首先说说中序遍历，对于一个二叉搜索树，对其进行中序遍历，就是相当于将所有节点按照从小到大的顺序排列出来。
所以题目给我们的一个上升的数组，很明显就是中序遍历的结果。

并且，说的是高度平衡的二叉树，即左右子树高度绝对值差不超过一，那么很容易就能推断出，整个树的根节点，就是这个有序数组的中点。

我们每次找到了中点，就能将数组拆分成左子树和右子树两个部分，然后再分别对这两个部分进行拆分，就可以达到还原的目的。

public TreeNode sortedArrayToBST(int[] nums) {
        int n = nums.length;
        if (n == 0) return null;
        return getTree(nums, 0, n - 1);
    }

public TreeNode getTree(int[] nums, int start, int end) {
	//终止条件，递归最重要的部分之一
        if (start == end) {
            return null;
        }
	//取数组的中点
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(nums[mid]);
	//通过参数控制，将数组拆分成左右两个部分
        root.left = getTree(nums, start, mid);
        root.right = getTree(nums, mid + 1, end);
        return root;
    }

由于给的是数组，所以找中点非常容易。
时间复杂度：O(N)，只需要对每个结点进行一次操作。
空间复杂度为：尼玛的，这种题我也不知道怎么说，我并没有用额外的空间来进行辅助存储，那是不是该O(1)？但是对于每一个节点，我都new了一个节点出来，那是不是该O(N)? 递归栈的占用的空间： O(logN)

第二题

这次给的不是数组了，变成了链表。本质还是完全一样，通过找中点，将链表进行拆分。不过对于链表，我们通过快慢指针的方式来进行中点的查找。并且，链表不能完全通过参数控制，来完全的分离。在找到中点时，我们还得进行一些操作，让中点的前驱的next变为null。

public TreeNode sortedListToBST(ListNode head) {
	//找中点
        ListNode mid = getMid(head);
        if (mid == null) return null;
        TreeNode root = new TreeNode(mid.val);
        //此节点没有子节点了
        if (head == mid) return root;
        root.right = sortedListToBST(mid.next);
        root.left = sortedListToBST(head);
        return root;
    }

public ListNode getMid(ListNode node) {
        ListNode fast = node;
        ListNode slow = node;
	//记录慢指针的前驱
        ListNode preSlow = null;
        if (node == null) return null;
        while (fast != null && fast.next != null) {
            preSlow = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        if (preSlow != null) {
	    //将中点的前驱的next赋值null，切断链表。
            preSlow.next = null;
        }
        return slow;
    }

时间复杂度，由于对链表的中点会进行查找，但是每次查找的长度都是前一次的二分之一，所以为O(N*logN)
空间复杂度：同上吧，我有点搞不懂