Related: LeetCode 109 - Convert Sorted List to Balanced Binary Search Tree (BST)
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
https://discuss.leetcode.com/topic/20983/java-recursive-solution/2
I get overflow problems at first because I didn't use mid - 1 and mid + 1 as the bound
Also check http://www.geeksforgeeks.org/sorted-array-to-balanced-bst/
https://discuss.leetcode.com/topic/14412/java-iterative-solution/2
There is a queue under the hood. And also a small data type encapsulate necessary info. Briefly, we assemble the tree from upper level to lower level, from left sibling to rightmost sibling.
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35218/Java-Iterative-Solution
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35440/Iterative-Java-Solution-Using-Stack
Read full article from LeetCode - Convert Sorted Array to Binary Search Tree | Darren's Blog
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
We can pick as the root the number at the center of the array, and recursively generate its left subtree by using the left half of the array, and generate its right subtree by using the right half of the array. After that, we just need to link the subtrees to the root.
https://discuss.leetcode.com/topic/20983/java-recursive-solution/2
I get overflow problems at first because I didn't use mid - 1 and mid + 1 as the bound
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length ==0){
return null;
}
return getTreeNode(nums, 0, nums.length-1);
}
private TreeNode getTreeNode(int[] nums, int start, int end){
if (start > end){
return null;
}
int middle = start + (end-start)/2;
TreeNode n = new TreeNode(nums[middle]);
n.left = getTreeNode(nums, start, middle-1);
n.right = getTreeNode(nums, middle+1, end);
return n;
}Also check http://www.geeksforgeeks.org/sorted-array-to-balanced-bst/
public TreeNode sortedArrayToBST(int[] num) {
if (num == null || num.length == 0)
return null;
return recursiveSortedArrayToBST(num, 0, num.length);
}
private TreeNode recursiveSortedArrayToBST(int[] num, int leftIndex, int rightIndex) {
if (leftIndex > rightIndex) // Empty tree
return null;
if (leftIndex == rightIndex) // Single-node tree
return new TreeNode(num[leftIndex]);
// Pick the number at the center as the root
int centerIndex = (leftIndex+rightIndex) / 2;
TreeNode root = new TreeNode(num[centerIndex]);
// Recursively convert the left half as the left subtree,
// and convert the right half as the right subtree
TreeNode left = recursiveSortedArrayToBST(num, leftIndex, centerIndex-1);
TreeNode right = recursiveSortedArrayToBST(num, centerIndex+1, rightIndex);
// Link the left subtree and the right subtree to the root
root.left = left;
root.right = right;
return root;
}
Iterative Version:https://discuss.leetcode.com/topic/14412/java-iterative-solution/2
There is a queue under the hood. And also a small data type encapsulate necessary info. Briefly, we assemble the tree from upper level to lower level, from left sibling to rightmost sibling.
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
Queue<MyNode> queue = new LinkedList<>();
int left = 0;
int right = nums.length - 1;
int val = nums[left + (right - left) / 2];
TreeNode root = new TreeNode(val);
queue.offer(new MyNode(root, left, right));
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
MyNode cur = queue.poll();
int mid = cur.lb + (cur.rb - cur.lb) / 2;
if (mid != cur.lb) {
TreeNode leftChild = new TreeNode(nums[cur.lb + (mid - 1 - cur.lb) / 2]);
cur.node.left = leftChild;
queue.offer(new MyNode(leftChild, cur.lb, mid - 1));
}
if (mid != cur.rb) {
TreeNode rightChild = new TreeNode(nums[mid + 1 + (cur.rb - mid - 1) / 2]);
cur.node.right = rightChild;
queue.offer(new MyNode(rightChild, mid + 1, cur.rb));
}
}
}
return root;
}
private static class MyNode {
TreeNode node;
int lb;
int index;
int rb;
public MyNode(TreeNode n, int theLeft, int theRight) {
this.node = n;
this.lb = theLeft;
this.rb = theRight;
}
}https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35218/Java-Iterative-Solution
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35440/Iterative-Java-Solution-Using-Stack
class Node{ // need another class to store multi information
int low, up; // means the TreeNode covers [low, up], low and up are all index
TreeNode t;
Node(int l, int p, TreeNode node){
low = l;
up = p;
t = node;
}
}
public TreeNode sortedArrayToBST(int[] num) {
if(num == null || num.length == 0) return null;
Stack<Node> stack = new Stack<Node>();
// initialize
TreeNode root = new TreeNode(num[(num.length-1)/2]);
Node rootNode = new Node(0,num.length-1,root);
stack.push(rootNode);
// iteration
while(!stack.isEmpty()){
Node node = stack.pop();
int middle = (node.low+node.up)/2; // cut half for [low, up]
// [low, middle-1]
if(middle-1 >= node.low){
TreeNode leftnode = new TreeNode(num[(middle-1+node.low)/2]);
node.t.left = leftnode;
Node left = new Node(node.low, middle-1, leftnode);
stack.push(left);
}
// [middle+1, up]
if(middle+1 <= node.up){
TreeNode rightnode = new TreeNode(num[(middle+1+node.up)/2]);
node.t.right = rightnode;
Node right = new Node(middle+1, node.up, rightnode);
stack.push(right);
}
}
return root;
}
private class Node {
TreeNode node;
int left, right;
public Node(TreeNode node, int left, int right) {
this.node = node;
this.left = left;
this.right = right;
}
}
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) return null;
TreeNode root = new TreeNode(0);
Stack<Node> stack = new Stack<>();
Node node = new Node(root, 0, nums.length - 1);
stack.push(node);
while (!stack.isEmpty()) {
Node cur = stack.pop();
int mid = cur.left + (cur.right - cur.left) / 2;
cur.node.val = nums[mid];
if (cur.left < mid) {
cur.left = new TreeNode(0);
stack.push(new Node(cur.left, cur.left, mid - 1));
}
if (cur.right > mid) {
cur.right = new TreeNode(0);
stack.push(new Node(cur.right, mid + 1, cur.right));
}
}
return root;
}public TreeNode sortedArrayToBST(int[] num) { if (num == null || num.length == 0) { return null; } if (num.length == 1) { return new TreeNode(num[0]); } Deque<Pair> queue = new ArrayDeque<>(); TreeNode root = new TreeNode(num[(num.length - 1) / 2]); queue.add(new Pair(0, num.length - 1, root)); while (!queue.isEmpty()) { Pair pair = queue.poll(); int pre = pair.pre; int post = pair.post; int curr = (post + pre) / 2; TreeNode tNode = pair.node; if (curr > pre) { TreeNode left = new TreeNode(num[(curr - 1 + pre) / 2]); tNode.left = left; queue.add(new Pair(pre, curr - 1, left)); } if (post > curr) { TreeNode right = new TreeNode(num[(post + curr + 1) / 2]); tNode.right = right; queue.add(new Pair(curr + 1, post, right)); } } return root; } private static class Pair { int pre; int post; TreeNode node; public Pair(int pre, int post, TreeNode node) { this.pre = pre; this.post = post; this.node = node; } }https://www.snip2code.com/Snippet/29145/Convert-Sorted-Array-to-Binary-Search-Tr
Read full article from LeetCode - Convert Sorted Array to Binary Search Tree | Darren's Blog
