[LeetCode] Convert Sorted Array to Binary Search Tree
文章目录
Convert Sorted Array to Binary Search Tree With Minimal Height
Given a sorted (increasing order) array, Convert it to create a binary
tree with minimal height. Notice There may exist multiple valid
solutions, return any of them.
Divide-Conquer
Time Complexity
O(N)
Space Complexity
O(logn)
思路
根据Binary Search Tree的性质,问题转化为找一个sorted array里的中位数,用一个helper函数,divide and conquer一路找中点,再通过前序遍历的方法把tree build起来
代码
public TreeNode sortedArrayToBST(int[] A) {
// write your code here
//corner case
if(A == null || A.length == 0) return null;
return helper(A, 0, A.length - 1);
}
private TreeNode helper(int[] A, int left, int right){
//base case
//preorder
if(left > right) return null;
int mid = left + (right - left)/2;
TreeNode node = new TreeNode(A[mid]);
node.left = helper(A, left, mid - 1);
node.right = helper(A, mid + 1, right);
return node;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论