Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
题意：给一个升序排好的数组，构造一棵二叉查找树或者叫二叉搜索树BST，要求这颗树是平衡的
BST：二叉查找树，左子树所有节点都小于根节点。右子树所有节点都大于根节点，递归定义
堆（大根堆和小根堆）对应的二叉树：根节点大于所有节点（大根堆），递归定义
解题思路：
1.选数组中间元素插入到BST中。递归实现
2.如果value大于root插入右子树，value小于root插入左子树。递归实现
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode root ; public TreeNode sortedArrayToBST(int[] num) {
if(num.length == 0)
return root;
if(1 == num.length){
return new TreeNode(num[0]);
}
int middle = num.length / 2;
root = new TreeNode(num[middle]); createBST(num, 0, middle - 1);
createBST(num, middle + 1, num.length - 1);
return root;
} /**
* 根据num数组，创建一棵二叉查找树
* @param num
* @param start
* @param end
*/
private void createBST(int num[], int start, int end){
int middle = 0;
if(start <= end && start >= 0 && end <num.length){
middle = (start + end) / 2; insertNode(root, num[middle]); createBST(num, start, middle - 1);
createBST(num, middle + 1, end);
}
} /**
* 向root所指的BST二叉查找树中插入value
* @param root
* @param value
*/
private void insertNode(TreeNode root, int value){
if(value > root.val){ //比根节点大,在右子树插入
if(root.right == null){
root.right = new TreeNode(value);
}else{
root = root.right;
insertNode(root, value);
}
}
else{
if(root.left == null){
root.left = new TreeNode(value);
}else{
root = root.left;
insertNode(root, value); //比根节点小的插入左子树
}
}
} // /**
// * 先序遍历
// * @param root
// */
// public void preTravel(TreeNode root){
// if(root != null){
// System.out.print(root.val + " ");
// preTravel(root.left);
// preTravel(root.right);
// }
// }
}
涉及到树的，很多都会用到递归实现，DFS，先序遍历等遍历...