每日一题——LeetCode109 有序链表转换二叉搜索树

题目

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一

题目要求我们将一个有序链表转换为高度平衡二叉搜索树，这里我们先见问题简化一下，假设现在问题为有序数组转换为高度平衡二叉搜索树，首先我们明确高度平衡二叉树要求任意结点左右两边子树高度相差不大于1，其次二叉搜索树也要求中序遍历为有序数组(左子树小于根节点，右子树大于根节点)。

这样不难想到，在构建树时，使用二分法，每次找到有序数组中心元素，使它作为根节点（中心元素左边的数组元素都小于它，右边的数组元素都大于它，并且它们之间数量差异小于等于1），然后我们将左边的子数组用于构建左子树，右边子数组用于构建右子树，构建子树时利用同样的方法构建即可。

但这题提供给我们的为有序链表，这样就不能直接使用二分法来获取中心元素，而是需要进行一次遍历，这里可以利用快慢指针寻找中心元素，快指针每次前进两步，慢指针每次前进一步，当快指针指向链表末尾时，慢指针真好为中心元素：

ListNode * getMid(ListNode * left, ListNode * right){  // 链表的首尾
	ListNode * f, *s;  // 快慢指针
	f=s=left;
	while(f!=right&& f->next!=right){
		f = f->next->next;
		s = s->next;
	}
	return s;
}

完整代码如下：

class Solution {
public:
    ListNode* getMid(ListNode * left, ListNode * right){ // 寻找中心元素
        ListNode * f, * s;
        f=s=left;
        while(f!=right && f->next!=right){
            f = f->next->next;
            s = s->next;
        }
        return s;
    }
    TreeNode* makeTree(ListNode * left, ListNode * right){ // 构建树
        if(left==right) return nullptr;
        ListNode * mid = getMid(left, right);  // 找到中心元素
        TreeNode * Node = new TreeNode(mid->val);  // 创建根节点
        Node->left = makeTree(left, mid);   // 构建左右子树
        Node->right = makeTree(mid->next, right);
        return Node;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        return makeTree(head, nullptr);
    }
};

复杂度分析
时间复杂度：O(n*logn)，n为链表中节点个数，构建二叉树需要遍历所有节点为O(n)，每次遍历时需要找到中位数为O(logn)
空间复杂度：O(logn)，递归调用栈，主要与树的高度有关，这里是平衡二叉树，故为O(logn)

解法二

解法一所用的方法为了找有序链表的中间元素进行了重复遍历，而二叉搜索树的中序遍历即为有序链表，那么可不可以利用这个信息来优化解法一呢？

之前解法一每次都要先对根节点进行赋值，再构建左右子树，从而每次都要先找到链表的中心元素。可以利用中序遍历的思想，构建根节点先不赋值(由构造函数赋初值)，进行中序遍历，找到最左边的节点，它所对应的就是链表的第一个元素，链表指针指向下一节点，往前回溯构造节点。

具体代码如下：

class Solution {
public:
    int getLength(ListNode* head){  // 得到链表长度
        int len=0;
        while(head!=nullptr){
            head=head->next;
            len++;
        }
        return len;
    }
    TreeNode* makeTree(ListNode*& head, int left, int right){ // 构建树
    	// 需要注意的是传入的head指针为引用传递
        if(head==nullptr || left>right)   return nullptr;
        int mid=(left+right)/2;  // 找到中心节点，方便后续划分左右子树数据
        TreeNode * Node = new TreeNode();  // 构建结点不赋值
		// 中序遍历
        Node->left = makeTree(head, left, mid-1);  // 左子树
        Node->val = head->val;  // 当前链表指针指向的值即为该节点值
        head = head->next;  // 链表往后移一个节点
        Node->right = makeTree(head, mid+1, right);  // 右子树
        return Node;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        int n=getLength(head);
        return makeTree(head, 0, n-1);
    }
};

复杂度分析
时间复杂度：O(n)
空间复杂度：O(logn)