[每日一题] 136. 有序链表转换二叉搜索树(BST树、递归、多方法）

1. 题目来源

链接：将有序数组转换为二叉搜索树
来源：LeetCode

2. 题目说明

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

• 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

说明：

你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例1：

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例2：

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

3. 题目解析

方法一：快慢指针法、内部递归法

这道题是要求把有序链表转为二叉搜索树，和上一道思路完全一样，只不过是操作的数据类型有所差别，一个是数组，一个是链表。数组方便就方便在可以通过 index 直接访问任意一个元素，而链表不行。

由于二分查找法每次需要找到中点，而

• 链表的查找中间点可以通过快慢指针来操作找到中点后
• 以中点的值建立一个树的根节点，
• 把原链表断开，分为前后两个链表，都不能包含原中节点，然后再分别对这两个链表递归调用原函数，分别连上左右子节点即可。

参见代码如下：

// 执行用时 :20 ms, 在所有 C++ 提交中击败了97.62%的用户
// 内存消耗 :24.6 MB, 在所有 C++ 提交中击败了37.78%的用户

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedListToBST(ListNode* head) {
        if (!head) 
            return NULL;
        if (!head->next) 
            return new TreeNode(head->val);
        ListNode *slow = head, *fast = head, *last = slow;
        while (fast->next && fast->next->next) {
            last = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        last->next = NULL;
        TreeNode *cur = new TreeNode(slow->val);
        if (head != slow) 
            cur->left = sortedListToBST(head);
        cur->right = sortedListToBST(fast);
        return cur;
    }
};

方法二：外部递归法

也可以采用如下的递归方法：

• 重写一个递归函数，有两个输入参数子链表的起点和终点
• 知道了这两个点，链表的范围就可以确定了

而直接将中间部分转换为二叉搜索树即可，递归函数中的内容跟上面解法中的极其相似

参见代码如下：

// 执行用时 :32 ms, 在所有 C++ 提交中击败了69.24%的用户
// 内存消耗 :24.9 MB, 在所有 C++ 提交中击败了22.57%的用户

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) 
            return NULL;
        return helper(head, NULL);
    }
    TreeNode* helper(ListNode* head, ListNode* tail) {
        if (head == tail) 
            return NULL;
        ListNode *slow = head, *fast = head;
        while (fast != tail && fast->next != tail) {
            slow = slow->next;
            fast = fast->next->next;
        }
        TreeNode *cur = new TreeNode(slow->val);
        cur->left = helper(head, slow);
        cur->right = helper(slow->next, tail);
        return cur;
    }
};