import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
*
* Source : https://oj.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.
*
*/
public class ConvertSortedArray {
/**
* 把一个已排序的数组转化我一颗高度平衡二叉搜索树，即AVL树，具有以下性质：
* 它是一棵空树或者左右两个子树的高度差不超过1，并且左右子树也都是AVL树
*
* 因为是已排序的数组，只需要找到数组中间位置的值作为根节点，左边的为左子树，右边的为右子树，递归构造即可
*
* @param arr
* @param left
* @param right
* @return
*/
public TreeNode convert (int[] arr, int left, int right) {
if (left > right) {
return null;
}
int mid = (left + right) / 2;
TreeNode root = new TreeNode(arr[mid]);
root.leftChild = convert(arr, left, mid-1);
root.rightChild = convert(arr, mid+1, right);
return root;
}
public void binarySearchTreeToArray (TreeNode root, List<Character> chs) {
if (root == null) {
chs.add('#');
return;
}
List<TreeNode> list = new ArrayList<TreeNode>();
int head = 0;
int tail = 0;
list.add(root);
chs.add((char) (root.value + '0'));
tail ++;
TreeNode temp = null;
while (head < tail) {
temp = list.get(head);
if (temp.leftChild != null) {
list.add(temp.leftChild);
chs.add((char) (temp.leftChild.value + '0'));
tail ++;
} else {
chs.add('#');
}
if (temp.rightChild != null) {
list.add(temp.rightChild);
chs.add((char)(temp.rightChild.value + '0'));
tail ++;
} else {
chs.add('#');
}
head ++;
}
//去除最后不必要的
for (int i = chs.size()-1; i > 0; i--) {
if (chs.get(i) != '#') {
break;
}
chs.remove(i);
}
}
private class TreeNode {
TreeNode leftChild;
TreeNode rightChild;
int value;
public TreeNode(int value) {
this.value = value;
}
public TreeNode() {
}
}
public static void main(String[] args) {
ConvertSortedArray convertSortedArray = new ConvertSortedArray();
int[] arr = new int[]{1,2,3,4,5};
List<Character> chs = new ArrayList<Character>();
convertSortedArray.binarySearchTreeToArray(convertSortedArray.convert(arr, 0, arr.length-1), chs);
System.out.println(Arrays.toString(chs.toArray(new Character[chs.size()])));
}
}