LeetCode Convert Sorted List to Binary Search Tree-CSDN博客

本文链接：https://blog.csdn.net/FightForProgrammer/article/details/41986123

LeetCode Convert Sorted List to Binary Search Tree

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.

这题和上一题的用数组构建平衡二叉排序树比较类似，可以通过把List转换成Array之后在进行操作。具体用Array构建的方法见：

但是这种办法的时间和空间复杂度都是O(n)；

这里参考网上的办法有一个空间复杂度O(n)，时间复杂度为O(1)的算法

	TreeNode *sortedListToBST(ListNode *head)
	{
	    int len = 0;
        ListNode * node = head;
        while (node != NULL)
        {
            node = node->next;
            len++;
        }
        return buildTree(head, 0, len-1);
    }
    
    TreeNode *buildTree(ListNode *&node, int start, int end)
    {
        if (start > end) return NULL;
        int mid = start + (end - start)/2;
        TreeNode *left = buildTree(node, start, mid-1);
        TreeNode *root = new TreeNode(node->val);
        root->left = left;
        node = node->next;
        root->right = buildTree(node, mid+1, end);
        return root;
    }