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.
1.思路
平衡二叉樹滿足左子節(jié)點(diǎn)<根節(jié)點(diǎn)<右子節(jié)點(diǎn)造锅，并且左右子樹高度相差不超過(guò)1抱慌。而對(duì)平衡二叉樹進(jìn)行中序遍歷可以得到一個(gè)順序的結(jié)果。
那么在一個(gè)有序的數(shù)組中铝量，中位數(shù)就是二叉樹的根節(jié)點(diǎn)贡这，中位數(shù)左右兩邊遞歸下去就能分別找到子樹的根節(jié)點(diǎn)了茬末。
2.代碼實(shí)現(xiàn)
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return convert(nums, 0, nums.length - 1);
}
private TreeNode convert(int[] nums, int l, int r) {
if (l > r) return null;
int mid = l + ((r - l) >> 1);
TreeNode root = new TreeNode(nums[mid]);
root.left = convert(nums, l, mid - 1);
root.right = convert(nums, mid + 1, r);
return root;
}
}
