Keshawn_lu's Blog

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

字数统计: 349阅读时长: 1 min
2020/07/03 Share

题目简介:

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

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

示例:

1
2
3
4
5
6
7
8
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5

思路:

这题其实相当于给你一个中序遍历的序列,让你还原出二叉搜索树。

首先每次选择数组中间的点作为每个子树的根节点(保证左右子树的高度平衡)。

再递归构建左右子树即可。

tip:

  • 注意每次数组的左右边界问题

代码如下:

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
/**
* 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* dfs(vector<int>& nums, int left, int right){

if(left > right)
return NULL;

//选中间点作为root, 保持左右节点高度平衡
int mid = left + (right - left) / 2;

TreeNode* root = new TreeNode(nums[mid]); //根节点

//递归构建左右子树
root -> left = dfs(nums, left, mid - 1); //不能选mid
root -> right = dfs(nums, mid + 1, right);

return root;

}

TreeNode* sortedArrayToBST(vector<int>& nums) {

return dfs(nums, 0, nums.size() - 1);
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: