一. 题目描述
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
二. 题目分析
将二叉查找树进行中序遍历,就可以得到一个升序排序的数组,因此,一个已经排序的数组可以看做一个中序遍历得到的数组,要得到一个高度平衡的二叉查找树,可以使得左右子树的节点数尽可能相等。因此,可以采用二分法将数组分为两个子数组,中间值作为父节点,左边的子数组作为左子树,右边的子数组作为右子树进行递归,这样就可以得到一个高度平衡的二叉查找树。
三. 示例代码
#include <iostream>
#include <vector>
using namespace std;
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)
{
return generateBST(, num.size() - , num);
}
private:
TreeNode* generateBST(int left, int right, vector<int>& num)
{
if (left > right)
return nullptr;
else if (left == right)
return new TreeNode(num[left]);
else
{
int mid = (left + right) / ;
TreeNode* node = new TreeNode(num[mid]);
node->left = generateBST(left, mid - , num);
node->right = generateBST(mid + , right, num);
return node;
}
}
};
四. 小结
这道题的技巧主要在于二叉查找树的中序遍历就是一个升序的数组,因此,本题就是根据一个二叉查找树的中序构建一个二叉查找树,由于要求高度平衡,因此,可以考虑左右两个子树的结点个数相同,这样就可以得到唯一的一颗二叉查找树。