leetcode解题: Convert Sorted List to Binary Search Tree (109)

发表于 | 分类于

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

解法1：Divide and Conquer

按照题意是要构造一个balanced的BST,那么root一定是sorted list的中间的一个点。所以想到了linkedlist求中间点的算法。
如果中间点求到了，那么可以将原list分成左右两个子list，对于每一个子list做相应的操作，左面的list就是左子树，右面的list就是右子树。这是一种分治的思想
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * 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 == NULL) {
            return NULL;
        }
        if (head->next == NULL) {
            return new TreeNode(head->val);
        }
        ListNode* preMiddle = findPreMiddle(head);
        ListNode* right = preMiddle->next->next;
        TreeNode* root = new TreeNode(preMiddle->next->val);
        // break left and right
        preMiddle->next->next = NULL;
        preMiddle->next = NULL;
        TreeNode* leftTree = sortedListToBST(head);
        TreeNode* rightTree = sortedListToBST(right);
        root->left = leftTree;
        root->right = rightTree;
        return root;
    }
    ListNode* findPreMiddle(ListNode* head) {
        if (head == NULL) {
            return head;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast != NULL && fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

Java

1