77 Notes:
88 Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
99
10- Solution: Recursion.
10+ Solution: Recursion. 1. preorder
11+ 2. inorder
1112 */
13+
1214/**
1315 * Definition for binary tree
1416 * public class TreeNode {
1921 * }
2022 */
2123public class Solution {
22- public TreeNode sortedArrayToBST (int []num ) {
24+ public TreeNode sortedArrayToBST_1 (int []num ) {
2325return sortedArrayToBSTRe (num ,0 ,num .length -1 );
2426 }
2527public TreeNode sortedArrayToBSTRe (int []num ,int left ,int right ) {
@@ -31,4 +33,19 @@ public TreeNode sortedArrayToBSTRe(int[] num, int left, int right) {
3133node .right =sortedArrayToBSTRe (num ,mid +1 ,right );
3234return node ;
3335 }
36+ public TreeNode sortedArrayToBST (int []num ) {
37+ int []curidx =new int [1 ];
38+ curidx [0 ] =0 ;
39+ return sortedArrayToBSTRe1 (num ,num .length ,curidx );
40+ }
41+ public TreeNode sortedArrayToBSTRe1 (int []num ,int len ,int []curidx ) {
42+ if (len ==0 )return null ;
43+ if (len ==1 )return new TreeNode (num [curidx [0 ]++]);
44+ int mid =len /2 ;
45+ TreeNode left =sortedArrayToBSTRe1 (num ,mid ,curidx );
46+ TreeNode node =new TreeNode (num [curidx [0 ]++]);
47+ node .left =left ;
48+ node .right =sortedArrayToBSTRe1 (num ,len -1 -mid ,curidx );
49+ return node ;
50+ }
3451}
