由链表构造平衡二叉树

Description

给定一个排序好的链表，由此生成一棵平衡二叉树

思路

这是前面一道题的延伸，前面的题目是数组，这道题是链表
数组可以由下标来确定值，但是链表就不可以了，所以需要用其他更好的办法来解决
这里提供两种非常经典的解决方法，一种是用中序遍历的思想，一种是用快慢指针
参考如下：
http://blog.csdn.net/linhuanmars/article/details/23904937
https://discuss.leetcode.com/topic/35997/share-my-java-solution-1ms-very-short-and-concise

解

解前
先了解一下平衡二叉树：

它是一棵空树或者它的左右两个子树德高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
平衡二叉树必定是二叉搜索树

对应的数组构造平衡二叉树的解法

public TreeNode sortedArrayToBST(int[] nums) {
    return sortedArrayToBST(0,nums.length-1,nums);
}
private TreeNode sortedArrayToBST(int start, int end, int[] nums) {
    if(start>end)return null;
    int middle=(start+end)/2;
    TreeNode node=new TreeNode(nums[middle]);
    node.left=sortedArrayToBST(start,middle-1,nums);
    node.right=sortedArrayToBST(middle+1,end,nums);
    return node;
}

中序遍历思想
上面链接中理解起来比较绕，其实如果不用ArrayList，而用一个全局变量理解起来就很简单了;而且空间复杂度也不是O(lgn)，而是O(1)
因为二叉搜索树的中序遍历的就是有序的序列，那么利用中序遍历的思想，在中间新建节点，必然为一个小根节点，它的左子树为前面递归返回的节点，右子树为后面递归返回的节点，具体代码如下：

ListNode index=null;
public TreeNode sortedListToBST(ListNode head) {
    if (head==null)return null;
    index=head;
    int num=0;
    while (head!=null){
        num++;
        head=head.next;
    }
    return helper(0,num-1);
}
private TreeNode helper(int s, int e) {
    if(s>e)return null;
    int mid=(s+e)/2;
    TreeNode left=helper(s,mid-1);
    TreeNode node=new TreeNode(index.val);
    index=index.next;
    node.left=left;
    TreeNode right=helper(mid+1,e);
    node.right=right;
    return node;
}

然后链接中给出的代码只是将全局变量去除了：

public TreeNode sortedListToBST(ListNode head) {
    if (head==null)return null;
    ArrayList<ListNode>list=new ArrayList<>();
    list.add(head);
    int num=0;
    while (head!=null){
        num++;
        head=head.next;
    }
    return helper(0,num-1,list);
}
private TreeNode helper(int s, int e,ArrayList<ListNode>list) {
    if(s>e)return null;
    int mid=(s+e)/2;
    TreeNode left=helper(s,mid-1,list);
    TreeNode node=new TreeNode(list.get(0).val);
    node.left=left;
    list.set(0,list.get(0).next);
    TreeNode right=helper(mid+1,e,list);
    node.right=right;
    return node;
}

快慢指针
快慢指针的思想其实就是二分，对于一个有序链表，快指针走到尾部时，慢指针所指的便是根节点，那么从此处分开，前半部分作为根节点的左子树，后半部分作为根节点的右子树，继续递归

public TreeNode sortedListToBST(ListNode head) {
    if(head==null) return null;
    return toBST(head,null);
}
public TreeNode toBST(ListNode head, ListNode tail){
    ListNode slow = head;
    ListNode fast = head;
    if(head==tail) return null;
    
    while(fast!=tail&&fast.next!=tail){
        fast = fast.next.next;
        slow = slow.next;
    }
    TreeNode thead = new TreeNode(slow.val);
    thead.left = toBST(head,slow);
    thead.right = toBST(slow.next,tail);
    return thead;
}