108. Convert Sorted Array to Binary Search Tree - cocoder39/coco39_LC GitHub Wiki
108. Convert Sorted Array to Binary Search Tree
time complexity is O(number) and space complexity is O(height)
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
int sz = nums.size();
return helper(nums, 0, sz - 1);
}
TreeNode* helper(vector<int> &nums, int start, int end) {
if (start > end) {
return nullptr;
}
int mid = start + (end - start) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = helper(nums, start, mid - 1);
root->right = helper(nums, mid + 1, end);
return root;
}
};
solution 2 - bfs: build the tree from top down
time O(N), space O(width)
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
Queue<TreeNodeWrapper> q = new LinkedList<>();
int mid = nums.length / 2;
TreeNode root = new TreeNode(nums[mid]);
q.add(new TreeNodeWrapper(root, 0, nums.length - 1));
while (!q.isEmpty()) {
TreeNodeWrapper cur = q.remove();
int curIdx = cur.leftIdx + (cur.rightIdx - cur.leftIdx + 1) / 2;
TreeNode curTreeNode = cur.node;
if (curIdx - 1 >= cur.leftIdx) {
int idx1 = cur.leftIdx + (curIdx - 1 - cur.leftIdx + 1) / 2;
cur.node.left = new TreeNode(nums[idx1]);
q.add(new TreeNodeWrapper(cur.node.left, cur.leftIdx, curIdx - 1));
}
if (curIdx + 1 <= cur.rightIdx) {
int idx2 = curIdx + 1 + (cur.rightIdx - curIdx - 1 + 1) / 2;
cur.node.right = new TreeNode(nums[idx2]);
q.add(new TreeNodeWrapper(cur.node.right, curIdx + 1, cur.rightIdx));
}
}
return root;
}
private class TreeNodeWrapper {
TreeNode node;
int leftIdx; // index of left most leave
int rightIdx;
TreeNodeWrapper(TreeNode node, int leftIdx, int rightIdx) {
this.leftIdx = leftIdx;
this.rightIdx = rightIdx;
this.node = node;
}
}
}