将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
遍历树的两种方法：
DFS：先序遍历（左中右），中序遍历（中左右），后序遍历（左右中）
BFS：层次遍历
二叉搜索树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
中序遍历不能唯一确定一棵二叉搜索树。
先序和后序遍历不能唯一确定一棵二叉搜索树。
中序+后序、中序+先序可以唯一确定一棵二叉树。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums,0,nums.length-1);
}
public TreeNode helper(int[] num,int left,int right){
if(left > right) return null;
int p = left + (right - left)/2;
TreeNode root = new TreeNode(num[p]); //传参要加上数组nums
root.left = helper(num,left,p-1);
root.right = helper(num,p+1,right);
return root;
}
}
复杂度分析
时间复杂度：O(N)，每个元素只访问一次。
空间复杂度：O(N)，二叉搜索树空间 O(N)，递归栈深度 O(logN)。
平衡二叉树：
1.左子树是平衡二叉树。
2.右子树是平衡二叉树。
3.左右子树之间的深度不超过1.
给定一个二叉树，判断它是否是高度平衡的二叉树。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return helper(root) != -1;
}
public int helper(TreeNode root){ //返回值为bool，只能判断左子树，右子树是否为平衡二叉树，无法判断相差几，所以为int
if(root == null){
return 0;
}
int lh = helper(root.left);
int rh = helper(root.right);
if(Math.abs(rh-lh)>1||lh<0||rh<0){ //平衡二叉树的条件，还要判断左右子树
return -1;
}
return Math.max(lh,rh)+1;
}
}
