526互联

LeetCode 109 有序链表转换二叉树

发布时间 2023-04-13 16:47:16作者: 卑以自牧lq

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

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

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

示例 1:
图片名称

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

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

提示:

  • head 中的节点数在[0, 2 * 104] 范围内
  • -105 <= Node.val <= 105

思路：递归

  1. 先遍历链表，把所有的值存入数组
  2. 用二分的方式，取中间的值做为根节点(保证左右子树高度不超过1)
  3. 用步骤 1，2 继续求左右子树的根节点
TreeNode* sortedListToBST(ListNode* head) {
    vector<int> nums;
    while (head) {
        nums.push_back(head->val);
        head = head->next;
    }
    return helper(nums, 0, nums.size() - 1);
}
TreeNode* helper(vector<int> &nums, int l, int r) {
    if (l > r)
        return nullptr;
    int mid = (l + r) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = helper(nums, l, mid - 1);
    root->right = helper(nums, mid + 1, r);
    return root;
}