【LeetCode】109. Convert Sorted List to Binary Search Tree 解法及注释，分治，递归

绝地灬酷狼 2022-07-29 11:38 161阅读 0赞

### 109. Convert Sorted List to Binary Search Tree    Total Accepted: 68081 Total Submissions: 224585 Difficulty: Medium ###

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

【分析】

这个题是对【LeetCode】108.Convert Sorted Array to Binary Search Tree的加深，同样是给定一个升序序列，建立平衡二叉搜索树，只是此题的升序序列存储结构为链表，而108题为数组，从实现难度来讲，并没有增加。

**解法一：**

基于108题，此题只需要增加一步，将链表结点数据域以数组的形式存储，如此，此题将完全退化为108题，但是，链表转化为数组的过程需要增加O(n)的空间复杂度，时间复杂度为O(nlgn).

**解法二：**

我按照解法一，几分钟便撸好代码一次性AC,但发现效率不是很高，后来我在网上看到了一个更为nice的解法，时间复杂度为：O(n),空间复杂度为：O(1).采用的是一种自底向上的建立方法，首先递归构建左子树，一直到左子树叶子结点，将链表第一个数据(1)赋给左叶子结点，然后移动链表指针，建立以该左叶子结点为根节点的右子树（该节点不可能再有左子树了，因为我们首先递归的是左子树），(1)对应的右子树为空，返回上一层，建立上一层“左叶子结点（便于理解，我们可这样认为)”，构建左叶子结点（2），然后构建该左叶子结点为根结点的右子树（3），然后（3）的左右皆为空，则返回上一层（2），再返回上一层...

![Center][]

【C++代码】

**解法一：运行时间28ms，Your runtime beats 29.80% of cppsubmissions**

class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) 
        {
            vector<int> nodeValue;
            if(head==NULL)return NULL;
            while(head!=NULL)
            {
                nodeValue.push_back(head->val);
                head=head->next;
            }
            return estiblishTree(nodeValue,0,nodeValue.size()-1);
        }
        
        TreeNode* estiblishTree(vector<int>& nodeValue,int start,int end)
        {
            if(start<=end)
            {
                int mid=start+((end-start)>>1);
                TreeNode* root=new TreeNode(nodeValue[mid]);
                root->left=estiblishTree(nodeValue,start,mid-1);
                root->right=estiblishTree(nodeValue,mid+1,end);
                return root;
            }
            return NULL;
        }
    };

**解法二：运行时间亦为28ms,Your runtime beats 29.80% of cppsubmissions**

class Solution {
    public:
        TreeNode *sortedListToBST(ListNode *head)
    	{
    	    int length = 0;
            ListNode * node = head;
            while (node != NULL)//遍历确认链表长度
            {
                node = node->next;
                length++;
            }
            return estiblishTree(head, 0, length-1);
        }
        //自底向上构建平衡搜索二叉树
        TreeNode *estiblishTree(ListNode *&node, int start, int end)
        {
            if (start > end) return NULL;
            int mid = start + (end - start)/2;
            TreeNode *left = estiblishTree(node, start, mid-1);
            TreeNode *root = new TreeNode(node->val);
            root->left = left;
            node = node->next;
            root->right = estiblishTree(node, mid+1, end);
            return root;
        }
    };

[Center]: /images/20220724/9f72064ac04b427680110f2f6b95e117.png