（每日一练C++）109. 有序链表转换二叉搜索树

心已赠人 2023-10-04 18:28 1阅读 0赞

[109. 有序链表转换二叉搜索树][109.]

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

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

示例 1:

输入: head = \[-10,-3,0,5,9\]  
输出: \[0,-3,9,-10,null,5\]  
解释: 一个可能的答案是\[0，-3,9，-10,null,5\]，它表示所示的高度平衡的二叉搜索树。  
示例 2:

输入: head = \[\]  
输出: \[\]

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

class Solution {
    public:
        ListNode* getMedian(ListNode* left, ListNode* right) {
            ListNode* fast = left;
            ListNode* slow = left;
            while (fast != right && fast->next != right) {
                fast = fast->next;
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }
    
        TreeNode* buildTree(ListNode* left, ListNode* right) {
            if (left == right) {
                return nullptr;
            }
            ListNode* mid = getMedian(left, right);
            TreeNode* root = new TreeNode(mid->val);
            root->left = buildTree(left, mid);
            root->right = buildTree(mid->next, right);
            return root;
        }
    
        TreeNode* sortedListToBST(ListNode* head) {
            return buildTree(head, nullptr);
        }
    };
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-1-3/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[109.]: https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/