C语言重构【109】有序链表转换二叉搜索树

谁借莪１个温暖的怀抱￠ 2022-12-21 10:50 142阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
    
    本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
    
    示例:
    
    给定的有序链表： [-10, -3, 0, 5, 9],
    
    一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
    
          0
         / \
       -3   9
       /   /
     -10  5

#### 方案： ####

*  快慢指针寻找中点，断开后分为左右两段，递归

class Solution
    { 
    public:
        TreeNode *sortedListToBST(ListNode *head)
        { 
            if (head == NULL)
                return NULL;
            //如果右侧为空则只有一个节点，返回该节点即可
            if (head->next == NULL)
                return new TreeNode(head->val);
    
            ListNode *slow;
            ListNode *pre = head; //slow前一个节点
            ListNode *fast = head->next->next;
    
            //当fast还没有走到末尾的时候，继续走，最终找到链表中点
            while (fast != NULL && fast->next != NULL)
            { 
                pre = pre->next;
                fast = fast->next->next;
            }
            slow = pre->next;
            TreeNode *root = new TreeNode(slow->val);
            pre->next = NULL;
            root->left = sortedListToBST(head);
            root->right = sortedListToBST(slow->next);
    
            return root;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode