Task

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

Solution

  • 要想高度平衡，需要每个节点的左右子树中的节点数相同，即每个子树的根节点都选在该子树对应的数组区域的中心
  • 如图，每次递归时将数组二分并将二分点作为该子树的根节点 leetcode108
  • 时间复杂度：要遍历每一个节点是O(n)，处理每个节点是随机索引O(1)，故总时间复杂度是O(n)
  • 空间复杂度：取决于递归深度，O(logn)
  • 实现：
 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

// Runtime: 20 ms, faster than 67.87% of C++ online submissions for Convert Sorted Array to Binary Search Tree.
// Memory Usage: 20.6 MB, less than 74.67% of C++ online submissions for Convert Sorted Array to Binary Search Tree.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return convert(nums,0,nums.size()-1);
    }
private:
    TreeNode *convert(vector<int> &nums,int l,int r){
        //递归终点是空指针（没有节点）
        if(l>r) return static_cast<TreeNode *>(nullptr);
        //二分
        int m=(l+r)/2;
        TreeNode *root=new TreeNode(nums[m]);
        root->left=convert(nums,l,m-1);
        root->right=convert(nums,m+1,r);
        return root;
    }
};