将有序链表转成二叉搜索树系列

发表于 | 浏览 次

将有序数组转换成二叉搜索树

  1. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

1
2
3
4
5
6
7
8
9
Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = sortedArrayToBSTCore(nums, 0, nums.size()-1); 
        return root;
    }
    TreeNode* sortedArrayToBSTCore(const vector<int>& nums, int lo, int hi){
        if(lo > hi){
            return nullptr;
        }
        int mid = (lo + hi) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = sortedArrayToBSTCore(nums, lo, mid - 1);
        root->right = sortedArrayToBSTCore(nums, mid + 1, hi);
        return root;
    }
};

将二叉搜索树的根节点传引用进入建立二叉搜索树的函数和返回二叉搜索树的头结点的两种方法，后者更快，但是前者更好理解。

时间复杂度为O(logn)。

将有序链表转换成二叉搜索树

  1. Convert Sorted List to Binary Search Tree

Medium

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

1
2
3
4
5
6
7
8
9
Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

解法1：递归

二叉搜索树的性质：左子树上所有节点的值都小于等于根节点的值，右子树上所有节点的值都大于等于根节点的值。一棵二叉搜索树的左子树和右子树都是二叉搜索树。

给定有序中的中间元素形成二叉搜索树的根节点。根节点左边的节点递归地形成左子树，根节点右的节点递归地形成右子树。这保证了二叉搜索树是平衡的。

思路：首先用快慢双指针找到根节点，然后递归地形成左子树和右子树。

AC代码1

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
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(head==nullptr){
           return nullptr;
        }
        ListNode* mid = findMiddleNode(head);
        TreeNode* root = new TreeNode(mid->val);
        if(head == mid){ 
            return root;
        }
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(mid->next);
        return root;
    }
    ListNode* findMiddleNode(ListNode*& head){
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            pre = slow;
            slow = slow->next;
        }
        if(pre!=nullptr){
            pre->next = nullptr;
        }
        
        // 当链表中只有两个元素时，slow指向尾节点
        return slow;
    }
};

AC代码2

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
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(head==nullptr){
           return nullptr;
        }
        ListNode* mid = findMiddleNode(head);
        TreeNode* root = new TreeNode(mid->val);
        if(head != mid){ // 当mid不指向链表中的第一个元素时，即左子树上还有节点时
            root->left = sortedListToBST(head);            
        }
        root->right = sortedListToBST(mid->next);
        return root;
    }
    ListNode* findMiddleNode(ListNode*& head){
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* fast = head == nullptr ? nullptr : head->next;
        ListNode* slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            pre = slow;
            slow = slow->next;
        }
        if(pre!=nullptr){
            pre->next = nullptr;
        }
        // 当链表中只有两个元素时，slow指向头节点
        return slow;
    }
};

两种AC代码的唯一一点小差别在与，寻找中间节点时，当链表中有两个节点时，第一种AC代码返回的是尾节点，而第二种代码返回的是头节点。

时间复杂度为O(nlongn)。假设链表中有n个元素。寻找中间元素需要线性遍历链表，slow指针需要从头节点移动到中间节点，时间复杂度为O(n)。接下来规模为n问题变成两个规模为n/2的子问题。因此，时间复杂度递推公式为:
T(n) = O(n) + 2 * T(n/2)
最后的时间复杂度为O(nlogn)。
空间复杂度为O(logn)。

解法2：转成有序数组

先将有序链表转成有序数组，然后使用第一题的解法解决。

时间复杂度为O(n)。空间复杂度为O(n)。

解法3：中序模拟

此解法基于这一事实：二叉搜索树的中序便利序列是有序的。

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
class Solution {
public:
    int findSize(ListNode* head){
        ListNode* node = head;
        int c = 0;
        while(node!=nullptr){
            node = node->next;
            c += 1;
        }
        return c;
    }
    TreeNode* convertListToBST(ListNode*& head, int l,int r){
        if(l > r){
            return nullptr;
        }
        int mid = (l + r) / 2;
        TreeNode* left = convertListToBST(head, l, mid - 1);
        TreeNode* node = new TreeNode(head->val);
        node->left = left;
        head = head->next;
        node->right = convertListToBST(head, mid + 1, r);
        return node;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        int size = findSize(head);
        return convertListToBST(head, 0, size - 1);
    }
};

时间复杂度为O(n)，空间复杂度为O(logn)。