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

题目

给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差不超过 1。

示例 1：
[中等] 109. 有序链表转换二叉搜索树 - 图1

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

解答 & 代码

递归分治：将链表区间 [head, tail) 构建为二叉搜索树

  1. 找到中间节点 mid：快慢指针法
  2. 根据中间节点 mid 的值建立二叉搜索树的根节点 root
  3. 递归将左半边链表构建为二叉搜索树，作为根节点 root 的左子树，即 root->left = dfsBuildTree(head, mid)
  4. 递归将右半边链表构建为二叉搜索树，作为根节点 root 的右子树，即 root->right = dfsBuildTree(mid->next, tail)

  5. 返回根节点 root

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode() : val(0), next(nullptr) {}
    7. *     ListNode(int x) : val(x), next(nullptr) {}
    8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. /**
    12. * Definition for a binary tree node.
    13. * struct TreeNode {
    14. *     int val;
    15. *     TreeNode *left;
    16. *     TreeNode *right;
    17. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    18. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    19. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    20. * };
    21. */
    22. class Solution {
    23.  // 快慢指针法查找链表中间节点，并返回
    24.  ListNode* findMidNode(ListNode* head, ListNode* tail)
    25.  {
    26.      ListNode* slow = head;
    27.      ListNode* fast = head;
    28.      while(fast != tail && fast->next != tail)
    29.      {
    30.          slow = slow->next;
    31.          fast = fast->next->next;
    32.      }
    33.      return slow;
    34.  }
    36.  // 递归分治，将链表区间 [head, tail) 构建为二叉搜索树
    37.  TreeNode* dfsBuildTree(ListNode* head, ListNode* tail)
    38.  {
    39.      // 递归结束条件：区间为空，直接返回空节点
    40.      if(head == tail)
    41.          return nullptr;
    43.      // 1. 找到链表中间节点
    44.      ListNode* mid = findMidNode(head, tail);
    45.      // 2. 建立根节点
    46.      TreeNode* root = new TreeNode(mid->val);
    47.      // 3. 递归将左半边链表构建为二叉搜索树，作为根节点 root 的左子树
    48.      root->left = dfsBuildTree(head, mid);
    49.      // 4. 递归将右半边链表构建为二叉搜索树，作为根节点 root 的右子树
    50.      root->right = dfsBuildTree(mid->next, tail);
    51.      // 5. 返回根节点 root
    52.      return root;
    53.  }
    54. public:
    55.  TreeNode* sortedListToBST(ListNode* head) {
    56.      return dfsBuildTree(head, nullptr);
    57.  }
    58. };

    复杂度分析：设链表长为 N

  • 时间复杂度 O(N logN)：递归每个深度存在 2 个区间，空间复杂度 O(2logN)，每个区间查找中间节点时间复杂度 O(N)
  • 空间复杂度 O(logN)：递归栈深度

执行结果：

  1. 执行结果：通过
  3. 执行用时：28 ms, 在所有 C++ 提交中击败了 40.35% 的用户
  4. 内存消耗：27.5 MB, 在所有 C++ 提交中击败了 91.84% 的用户