Skip to content

Instantly share code, notes, and snippets.

@Jeffwan
Last active February 26, 2018 23:10
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Jeffwan/8982109 to your computer and use it in GitHub Desktop.
Convert Sorted Array to Binary Search Tree @leetcode
package leetcode.tree;
public class SortedArrayToBST {
/**
* Thought: In order to make it height BST, we can not insert node into tree from int[0].
* The problem is how to determine the root node --> middle. which makes left and right have same count nodes or +1.
*
* Use Binary Search thought to solve this problem. Difference is node take num[mid], so we need to change the index
* mid-1 and mid+1, what's more, start > end works but not start + 1 >= end. return null means leaf.left == null
*
* After we solve the root problem, the left subtree will be same problem. --> Divide & Conquer
*
* like 1 2 3 4 5 6 7 8 -- balanced
*
* 4
* 2 6
* 1 3 5 7
* 8
*
* Reference: http://leetcode.com/2010/11/convert-sorted-array-into-balanced.html
*
* @param num
* @return
*/
public TreeNode sortedArrayToBST(int[] num) {
if (num == null || num.length == 0) {
return null;
}
return helper(num, 0, num.length - 1);
}
private TreeNode helper(int[] num, int start, int end) {
if (start > end) {
return null;
}
// Binary Search Thought
int mid = start + (end - start) / 2;
TreeNode node = new TreeNode(num[mid]);
// Divide
node.left = helper(num, start, mid - 1);
node.right = helper(num, mid + 1, end);
// Conquer
return node;
}
// TreeNode
private class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode (int x) {
val = x;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment