leetcode---109. Convert Sorted List to Binary Search Tree C++题解

最新推荐文章于 2022-08-15 06:53:09 发布

宝宝可乖了

最新推荐文章于 2022-08-15 06:53:09 发布

阅读量304

点赞数

分类专栏： leetcode 文章标签： leetcode

本文链接：https://blog.csdn.net/Morzker/article/details/88554078

版权

leetcode 专栏收录该内容

12 篇文章

订阅专栏

本文介绍了一种高效算法，将有序链表转换为平衡二叉搜索树(BST)。通过分治策略，选取中间节点作为根，递归构建左右子树，最终形成平衡的BST。代码简洁，使用C++实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

109. Convert Sorted List to Binary Search Tree

C++，代码很简短。。。本来可以真的去构造AVL树，但是给的序列已经是有序的了，就没必要了。不然AVL写下来至少也得七八十行。。。

思路就是利用分治的思想，将中间结点作为分割点，分成左子树和右子树。

首先链表元素可以先用vector存一下，因为后面如果用链表再去找中间结点的话，很影响效率；
找到当前区间[left, right]的中间结点mid，构造为根结点；
然后再递归地构造根结点的左子树和右子树；
最后记得返回根结点。

代码如下：

typedef TreeNode* TNP;

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> list;
        ListNode *p = head;
        while (p) {
            list.push_back(p->val);
            p = p->next;
        }
        return pre(0, list.size() - 1, list);
    }
    
    TNP pre(int left, int right, vector<int> &list) {
        if (left > right) return NULL;
        int mid = (left + right) / 2;
        TNP root = new TreeNode(list[mid]);
        root->left = pre(left, mid - 1, list);
        root->right = pre(mid + 1, right, list);
        return root;
    }
};