34.【108】将有序数组转换为二叉搜索树
//将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
//
// 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
//
// 示例:
//
// 给定有序数组: [-10,-3,0,5,9],
//
//一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
//
// 0
// / \
// -3 9
// / /
// -10 5
//
// Related Topics 树 深度优先搜索
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums,0,nums.length-1);}public TreeNode sortedArrayToBST(int [] nums,int left,int right){if(left>right)return null; //边界条件，注意是left>rightint mid=(left+right)/2;TreeNode root=new TreeNode(nums[mid]);root.left=sortedArrayToBST(nums,left,mid-1); //递归向左探索，范围变成left~mid-1;root.right=sortedArrayToBST(nums,mid+1,right);return root;}
}
35.【110】 平衡二叉树
//给定一个二叉树，判断它是否是高度平衡的二叉树。
//
// 本题中，一棵高度平衡二叉树定义为：
//
//
// 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
//
//
// 示例 1:
//
// 给定二叉树 [3,9,20,null,null,15,7]
//
// 3
// / \
// 9 20
// / \
// 15 7
//
// 返回 true 。
//
//示例 2:
//
// 给定二叉树 [1,2,2,3,3,null,null,4,4]
//
// 1
// / \
// 2 2
// / \
// 3 3
// / \
// 4 4
//
//
// 返回 false 。
//
//
// Related Topics 树 深度优先搜索
class Solution {//这个ReturnNode是参考我描述的递归套路的第二步：思考返回值是什么//一棵树是BST等价于它的左、右俩子树都是BST且俩子树高度差不超过1//因此我认为返回值应该包含当前树是否是BST和当前树的高度这两个信息private class ReturnNode{boolean isB;int depth;public ReturnNode(int depth, boolean isB){this.isB = isB;this.depth = depth;}}//主函数public boolean isBalanced(TreeNode root) {return isBST(root).isB;}//参考递归套路的第三部：描述单次执行过程是什么样的//这里的单次执行过程具体如下：//是否终止?->没终止的话，判断是否满足不平衡的三个条件->返回值public ReturnNode isBST(TreeNode root){if(root == null){return new ReturnNode(0, true);}//不平衡的情况有3种：左树不平衡、右树不平衡、左树和右树差的绝对值大于1ReturnNode left = isBST(root.left);ReturnNode right = isBST(root.right);if(left.isB == false || right.isB == false){return new ReturnNode(0, false);}if(Math.abs(left.depth - right.depth) > 1){return new ReturnNode(0, false);}//不满足上面3种情况，说明平衡了，树的深度为左右俩子树最大深度+1return new ReturnNode(Math.max(left.depth, right.depth) + 1, true);}
}