109. Convert Sorted List to Binary Search Tree

Posted on | In , |

题目

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/

-w958

想法

感觉是一道很经典的题目..

生成一棵不平衡的，单侧的树，然后旋转嘛？有点傻，不过这也是一个问题，把单侧树转变为平衡树

渐进式的，跟那个随即抽取的有点像，不知道总共有多长

AVL tree和splay tree都忘了，尴尬，不行，复习平衡树，然后再做这道题，同时写一篇博客

这道题，题目的数据结构没有高度，所以判断是否平衡还是个麻烦，而且全部是RR的不平衡，应该有更专属的方式来解决

哎呀，看了别人的答案，无非就是二分、递归建树，自己想的可能有点偏orz

解答

参考了:

JosephTao: Share my JAVA solution, 1ms, very short and concise.
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35476/Share-my-JAVA-solution-1ms-very-short-and-concise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
private:
    TreeNode* helper(ListNode* l, ListNode* r) {
        if (l == r)
            return NULL;
        ListNode* slow = l;
        ListNode* fast = l;
        while (fast != r && fast->next != r) {
            fast = fast->next->next;
            slow = slow->next;
        }
        TreeNode* node = new TreeNode(slow->val);
        node->left = helper(l, slow);
        node->right = helper(slow->next, r);
        return node;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head)
            return NULL;
        return helper(head, NULL);
    }
};

回顾

分治的策略，在这种情况下还是很适用的，一开始觉得链表的话，不好进行分治，但是没想到这个答案竟然是beat 100%，有些吃惊。

学习到了一个二分链表的小trick:

1
2
3
4
while (fast != r && fast->next != r) {
    fast = fast->next->next;
    slow = slow->next;
}

还是蛮有趣的，如果是自己做的话，肯定是先数一遍size，然后定位到size/2，这样应该会快一点。