Fork me on GitHub

leetcode之108. 将有序数组转换为二叉搜索树

发表于 | 分类于
字数统计 267 字 | 阅读时长 1 分钟

题目描述：

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

1
2
3
4
5
6
7
8
9
10
> 给定有序数组: [-10,-3,0,5,9],
> 
> 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
> 
>       0
>      / \
>    -3   9
>    /   /
>  -10  5
>

解题思路：

时间复杂度：$O(n)$, 空间复杂度：$O(n)$.

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
/**
 * 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) {
           if(nums.size()==0) return NULL;
           int low = 0;
           int high = nums.size();
           TreeNode *root = sortToBst(nums, low, high-1);
           return root;
    }
        
      TreeNode* sortToBst(vector<int>&num, int low, int high)
      {
          if(low > high)
              return NULL;
          
          int mid = (low + high) / 2;
          TreeNode *t = new TreeNode(num[mid]);
          
          t->left =sortToBst(num, low, mid-1);
          t->right=sortToBst(num, mid+1, high);
          return t;
      }
        
    
};