https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
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
給你一個sorted array，請建立出相對應的BST，而且還要滿足"height balanced" (這邊定義為"對任一點來說，其左右子樹的高度不能差超過1" )[思路]
首先回想一下BST的規定:左子樹的node都小於root，右子樹的node都大於root。
然後從簡單的例子思考問題，原題中我們該挑哪一個當root ?
挑-10的話，剩下的人只能放在右子樹，左子樹甚麼都不能放，這樣無論如何不會平衡。
挑-3的話，剩下的0,5,9只能放在右子樹，左子樹只能放-10，這樣右子樹裡的人相比左子樹多太多了，左右不容易平衡(但不是不可能)。
挑0的話，剩下的人可以一半放右子樹，一半放左子樹，這樣左右子樹樹高比較容易平衡。
我們可以得到一個想法 : 既然樹高和node數目正相關，那麼我挑選root時，要盡量挑那種"可以把sorted array分成兩半的人"，這樣左右子樹的node數目就會相等(或頂多只差一)。
然後左半邊和右半邊可看成兩個獨立的sorted array，重複一樣的行為即可建出樹。
class Solution {
public:
TreeNode* buildBST(vector<int>& nums, int L, int R){
if(L>R) return NULL;// return NULL
else if(L<=R){
int mid=(L+R)/2;
TreeNode* newnode=new TreeNode(nums[mid]);
newnode->left=buildBST(nums,L,mid-1);
newnode->right=buildBST(nums,mid+1,R);
return newnode;
}
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return buildBST(nums, 0, nums.size()-1);
}
};
