FXTi's blog
0%

convert-sorted-array-to-binary-search-tree

Posted on Edited on

Convert Sorted Array to Binary Search Tree – LeetCode 108

Problem

Description

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

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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* sort(vector<int>::const_iterator start, vector<int>::const_iterator end){
        if(end == start) return nullptr;
        vector<int>::const_iterator it = start + (end-start) / 2;
        TreeNode *tmp = new TreeNode(*it);
        tmp->left = sort(start,it); tmp->right = sort(it+1,end);
        return tmp;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sort(nums.cbegin(),nums.cend());
    }
};

思路

要求将一个已经排序的数列转换成平衡的二叉搜索树，出于方便编码的考虑，优先用DFS写递归解，时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$13$ ms，排名$43.24\%$

Better

思路

用三个Queue来模拟栈上递归…比较好理解的BFS迭代解，时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$13$ ms，排名$43.24\%$

Code

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
/**
 * 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* sortedArrayToBST(vector<int>& nums) {
        int len = nums.size();
        if(len == 0) return nullptr;
        TreeNode *head = new TreeNode(0);
        
        queue<TreeNode *> node; node.push(head);
        queue<int> left; left.push(0);
        queue<int> right; right.push(len-1);
        
        while(!node.empty()){
            TreeNode *curr = node.front(); node.pop();
            int l = left.front(); left.pop();
            int r = right.front(); right.pop();
            int m = (l + r) / 2;
            curr->val = nums[m];
            if(l <= m - 1){
                curr->left = new TreeNode(0);
                node.push(curr->left);
                left.push(l);
                right.push(m-1);
            }
            if(m + 1 <= r){
                curr->right = new TreeNode(0);
                node.push(curr->right);
                left.push(m+1);
                right.push(r);
            }
        }
        
        return head;
    }
};