108. Convert Sorted Array to Binary Search Tree
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:
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
给定一个升序排列的数组,要构建一个高度平衡的二叉搜索树。 二叉搜索树的概念是递归定义的,具体可以参看维基百科,简单来说就是左孩子小于根节点,右孩子大于根节点。 但是本题要求二叉搜索树是高度平衡的,也就是说左右孩子的高度差不能大于1。 我一开始的想法是既然是平衡二叉搜索树,直接取数组中点,然后左右依次排开,肯定能得到一棵平衡二叉搜索树,如下左图所示。 但是这一版本的代码提交上去之后只通过了6个样例。后来仔细想了想,这解法未免也太简单幼稚了吧。想到之前解树的题都用到了递归,这题应该也可以用,立马灵光一闪,第一次取中点之后,递归的在左右半个数组中取中点建树,所有还可以得到如上右图所示的更加紧凑的平衡二叉搜索树。
完整代码如下:
class Solution {
public:
TreeNode* work(vector<int>& nums, int s, int t)
{
if (s == t)
return new TreeNode(nums[s]);
if (s > t)
return NULL;
int mid = (s + t + 1) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = work(nums, s, mid – 1);
root->right = work(nums, mid + 1, t);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) { return work(nums, 0, nums.size() – 1); }
};
本代码提交AC,用时16MS。
Pingback: LeetCode Convert Sorted List to Binary Search Tree | bitJoy > code