Solution:
Basic recursion question.
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedArrayToBST(int[] num) {
if (num.length == 0) return null;
if (num.length == 1) return new TreeNode(num[0]);
return buildBST(num, 0, num.length-1);
}
public TreeNode buildBST(int[] num, int first, int last){
if(first <= last){
int mid = (first + last)/2;
TreeNode root = new TreeNode(num[mid]);
root.left = buildBST(num, first, mid-1);
root.right = buildBST(num, mid+1, last);
return root;
}
return null;
}
}
No comments:
Post a Comment