我的书签
添加书签
移除书签题目描述（简单难度）
给一个升序数组，生成一个平衡二叉搜索树。平衡二叉树定义如下：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 二叉搜索树定义如下： 1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 3. 任意节点的左、右子树也分别为二叉查找树； 4. 没有键值相等的节点。
解法一 递归
如果做了 98 题 和 99 题，那么又看到这里的升序数组，然后应该会想到一个点，二叉搜索树的中序遍历刚好可以输出一个升序数组。 所以题目给出的升序数组就是二叉搜索树的中序遍历。 根据中序遍历还原一颗树，又想到了 105 题 和 106 题，通过中序遍历加前序遍历或者中序遍历加后序遍历来还原一棵树。前序（后序）遍历的作用呢？提供根节点！然后根据根节点，就可以递归的生成左右子树。 这里的话怎么知道根节点呢？平衡二叉树，既然要做到平衡，我们只要把根节点选为数组的中点即可。 综上，和之前一样，找到了根节点，然后把数组一分为二，进入递归即可。注意这里的边界情况，包括左边界，不包括右边界。 1. public TreeNode sortedArrayToBST(int[] nums) { 2. return sortedArrayToBST(nums, 0, nums.length); 3. } 4. 5. private TreeNode sortedArrayToBST(int[] nums, int start, int end) { 6. if (start == end) { 7. return null; 8. } 9. int mid = (start + end) >>> 1; 10. TreeNode root = new TreeNode(nums[mid]); 11. root.left = sortedArrayToBST(nums, start, mid); 12. root.right = sortedArrayToBST(nums, mid + 1, end); 13. 14. return root; 15. }
解法二 栈 DFS
递归都可以转为迭代的形式。
一部分递归算法，可以转成动态规划，实现空间换时间，例如 5题，10题，53题，72题，从自顶向下再向顶改为了自底向上。
一部分递归算法，只是可以用栈去模仿递归的过程，对于时间或空间的复杂度没有任何好处，比如这道题，唯一好处可能就是能让我们更清楚的了解递归的过程吧。
自己之前对于这种完全模仿递归思路写成迭代，一直也没写过，今天也就试试吧。
思路的话，我们本质上就是在模拟递归，递归其实就是压栈出栈的过程，我们需要用一个栈去把递归的参数存起来。这里的话，就是函数的参数 start，end，以及内部定义的 root。为了方便，我们就定义一个类。
1. class MyTreeNode {
2. TreeNode root;
3. int start;
4. int end
5. MyTreeNode(TreeNode r, int s, int e) {
6. this.root = r;
7. this.start = s;
8. this.end = e;
9. }
10. }
第一步，我们把根节点存起来。
1. Stack
然后开始递归的过程，就是不停的生成左子树。因为要生成左子树，end - start 表示当前树的可用数字的个数，因为根节点已经用去 1 个了，所以为了生成左子树，个数肯定需要大于 1。
1. while (end - start > 1) {
2. mid = (start + end) >>> 1; //当前根节点
3. end = mid;//左子树的结尾
4. mid = (start + end) >>> 1;//左子树的中点
5. curRoot.left = new TreeNode(nums[mid]);
6. curRoot = curRoot.left;
7. rootStack.push(new MyTreeNode(curRoot, start, end));
8. }
在递归中，返回 null 以后，开始生成右子树。这里的话，当 end - start <= 1 ，也就是无法生成左子树了，我们就可以出栈，来生成右子树。
1. MyTreeNode myNode = rootStack.pop();
2. //当前作为根节点的 start end 以及 mid
3. start = myNode.start;
4. end = myNode.end;
5. mid = (start + end) >>> 1;
6. start = mid + 1; //右子树的 start
7. curRoot = myNode.root; //当前根节点
8. if (start < end) { //判断当前范围内是否有数
9. mid = (start + end) >>> 1; //右子树的 mid
10. curRoot.right = new TreeNode(nums[mid]);
11. curRoot = curRoot.right;
12. rootStack.push(new MyTreeNode(curRoot, start, end));
13. }
然后把上边几块内容组合起来就可以了。
1. class MyTreeNode {
2. TreeNode root;
3. int start;
4. int end;
5. 6. MyTreeNode(TreeNode r, int s, int e) {
7. this.root = r;
8. this.start = s;
9. this.end = e;
10. }
11. }
12. public TreeNode sortedArrayToBST(int[] nums) {
13. if (nums.length == 0) {
14. return null;
15. }
16. Stack
解法三 队列 BFS
参考 这里。 和递归的思路基本一样，不停的划分范围。
1. class MyTreeNode {
2. TreeNode root;
3. int start;
4. int end;
5. 6. MyTreeNode(TreeNode r, int s, int e) {
7. this.root = r;
8. this.start = s;
9. this.end = e;
10. }
11. }
12. public TreeNode sortedArrayToBST3(int[] nums) {
13. if (nums.length == 0) {
14. return null;
15. }
16. Queue
最巧妙的地方是它先生成 left 和 right 但不进行赋值，只是把范围传过去，然后出队的时候再进行赋值。这样最开始的根节点也无需单独考虑了。
扩展 求中点
前几天和同学发现个有趣的事情，分享一下。
首先假设我们的变量都是 int 值。
二分查找中我们需要根据 start 和 end 求中点，正常情况下加起来除以 2 即可。
1. int mid = (start + end) / 2
但这样有一个缺点，我们知道int的最大值是 Integer.MAX_VALUE ，也就是2147483647。那么有一个问题，如果 start = 2147483645，end = 2147483645，虽然 start 和 end都没有超出最大值，但是如果利用上边的公式，加起来的话就会造成溢出，从而导致mid计算错误。
解决的一个方案就是利用数学上的技巧，我们可以加一个 start 再减一个 start 将公式变形。
1. (start + end) / 2 = (start + end + start - start) / 2 = start + (end - start) / 2
这样的话，就解决了上边的问题。
然后当时和同学看到jdk源码中，求mid的方法如下
1. int mid = (start + end) >>> 1
它通过移位实现了除以 2，但。。。这样难道不会导致溢出吗？
首先大家可以补一下 补码 的知识。
其实问题的关键就是这里了>>> ，我们知道还有一种右移是>>。区别在于>>为有符号右移，右移以后最高位保持原来的最高位。而 >>> 这个右移的话最高位补 0。
所以这里其实利用到了整数的补码形式，最高位其实是符号位，所以当 start + end 溢出的时候，其实本质上只是符号位收到了进位，而>>>这个右移不仅可以把符号位右移，同时最高位只是补零，不会对数字的大小造成影响。
但>>有符号右移就会出现问题了，事实上 JDK6 之前都用的>>，这个 BUG 在 java 里竟然隐藏了十年之久。
总
经过这么多的分析，大家估计体会到了递归的魅力了吧，简洁而优雅。另外的两种迭代的实现，可以让我们更清楚的了解递归到底发生了什么。关于求中点，大家以后就用>>>吧，比start + (end - start) / 2简洁不少，还能给别人科普一下补码的知识。
添加好友一起进步~
如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^
如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情
