1. 首页
  2. Leetcode经典148题

leetcode-108-Convert-Sorted-Array-to-Binary-Search-Tree

题目描述(简单难度)

leetcode-108-Convert-Sorted-Array-to-Binary-Search-Tree

给一个升序数组,生成一个平衡二叉搜索树。平衡二叉树定义如下:

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

二叉搜索树定义如下:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。

解法一 递归

如果做了 “>99 题,那么又看到这里的升序数组,然后应该会想到一个点,二叉搜索树的中序遍历刚好可以输出一个升序数组。

所以题目给出的升序数组就是二叉搜索树的中序遍历。

根据中序遍历还原一颗树,又想到了 “>106 题,通过中序遍历加前序遍历或者中序遍历加后序遍历来还原一棵树。前序(后序)遍历的作用呢?提供根节点!然后根据根节点,就可以递归的生成左右子树。

这里的话怎么知道根节点呢?平衡二叉树,既然要做到平衡,我们只要把根节点选为数组的中点即可。

综上,和之前一样,找到了根节点,然后把数组一分为二,进入递归即可。注意这里的边界情况,包括左边界,不包括右边界。

public TreeNode sortedArrayToBST(int[] nums) {
    return sortedArrayToBST(nums, 0, nums.length);
}

private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
    if (start == end) {
        return null;
    }
    int mid = (start + end) >>> 1;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums, start, mid);
    root.right = sortedArrayToBST(nums, mid + 1, end);

    return root;
}

解法二 栈 DFS

递归都可以转为迭代的形式。

一部分递归算法,可以转成动态规划,实现空间换时间,例如 “>10题“>72题,从自顶向下再向顶改为了自底向上。

一部分递归算法,只是可以用栈去模仿递归的过程,对于时间或空间的复杂度没有任何好处,比如这道题,唯一好处可能就是能让我们更清楚的了解递归的过程吧。

自己之前对于这种完全模仿递归思路写成迭代,一直也没写过,今天也就试试吧。

思路的话,我们本质上就是在模拟递归,递归其实就是压栈出栈的过程,我们需要用一个栈去把递归的参数存起来。这里的话,就是函数的参数 startend,以及内部定义的 root。为了方便,我们就定义一个类。

class MyTreeNode {
    TreeNode root;
    int start;
    int end 
    MyTreeNode(TreeNode r, int s, int e) {
        this.root = r;
        this.start = s;
        this.end = e;
    }
}

第一步,我们把根节点存起来。

Stack<MyTreeNode> rootStack = new Stack<>();
int start = 0;
int end = nums.length;
int mid = (start + end) >>> 1;
TreeNode root = new TreeNode(nums[mid]);
TreeNode curRoot = root;
rootStack.push(new MyTreeNode(root, start, end));

然后开始递归的过程,就是不停的生成左子树。因为要生成左子树,end - start 表示当前树的可用数字的个数,因为根节点已经用去 1 个了,所以为了生成左子树,个数肯定需要大于 1。

while (end - start > 1) {
    mid = (start + end) >>> 1; //当前根节点
    end = mid;//左子树的结尾
    mid = (start + end) >>> 1;//左子树的中点
    curRoot.left = new TreeNode(nums[mid]);
    curRoot = curRoot.left;
    rootStack.push(new MyTreeNode(curRoot, start, end));
}

在递归中,返回 null 以后,开始生成右子树。这里的话,当 end - start &lt;= 1 ,也就是无法生成左子树了,我们就可以出栈,来生成右子树。

MyTreeNode myNode = rootStack.pop();
//当前作为根节点的 start end 以及 mid
start = myNode.start;
end = myNode.end;
mid = (start + end) >>> 1;
start = mid + 1; //右子树的 start
curRoot = myNode.root; //当前根节点
if (start < end) { //判断当前范围内是否有数
    mid = (start + end) >>> 1; //右子树的 mid
    curRoot.right = new TreeNode(nums[mid]);
    curRoot = curRoot.right;
    rootStack.push(new MyTreeNode(curRoot, start, end));
}

然后把上边几块内容组合起来就可以了。

class MyTreeNode {
    TreeNode root;
    int start;
    int end;

    MyTreeNode(TreeNode r, int s, int e) {
        this.root = r;
        this.start = s;
        this.end = e;
    }
}
public TreeNode sortedArrayToBST(int[] nums) {
    if (nums.length == 0) {
        return null;
    }
    Stack<MyTreeNode> rootStack = new Stack<>();
    int start = 0;
    int end = nums.length;
    int mid = (start + end) >>> 1;
    TreeNode root = new TreeNode(nums[mid]);
    TreeNode curRoot = root;
    rootStack.push(new MyTreeNode(root, start, end));
    while (end - start > 1 || !rootStack.isEmpty()) {
        //考虑左子树
        while (end - start > 1) {
            mid = (start + end) >>> 1; //当前根节点
            end = mid;//左子树的结尾
            mid = (start + end) >>> 1;//左子树的中点
            curRoot.left = new TreeNode(nums[mid]);
            curRoot = curRoot.left;
            rootStack.push(new MyTreeNode(curRoot, start, end));
        }
        //出栈考虑右子树
        MyTreeNode myNode = rootStack.pop();
        //当前作为根节点的 start end 以及 mid
        start = myNode.start;
        end = myNode.end;
        mid = (start + end) >>> 1;
        start = mid + 1; //右子树的 start
        curRoot = myNode.root; //当前根节点
        if (start < end) { //判断当前范围内是否有数
            mid = (start + end) >>> 1; //右子树的 mid
            curRoot.right = new TreeNode(nums[mid]);
            curRoot = curRoot.right;
            rootStack.push(new MyTreeNode(curRoot, start, end));
        }

    }

    return root;
}

解法三 队列 BFS

参考 class MyTreeNode { TreeNode root; int start; int end; MyTreeNode(TreeNode r, int s, int e) { this.root = r; this.start = s; this.end = e; } } public TreeNode sortedArrayToBST3(int[] nums) { if (nums.length == 0) { return null; } Queue<MyTreeNode> rootQueue = new LinkedList<>(); TreeNode root = new TreeNode(0); rootQueue.offer(new MyTreeNode(root, 0, nums.length)); while (!rootQueue.isEmpty()) { MyTreeNode myRoot = rootQueue.poll(); int start = myRoot.start; int end = myRoot.end; int mid = (start + end) >>> 1; TreeNode curRoot = myRoot.root; curRoot.val = nums[mid]; if (start < mid) { curRoot.left = new TreeNode(0); rootQueue.offer(new MyTreeNode(curRoot.left, start, mid)); } if (mid + 1 < end) { curRoot.right = new TreeNode(0); rootQueue.offer(new MyTreeNode(curRoot.right, mid + 1, end)); } } return root; }

最巧妙的地方是它先生成 leftright 但不进行赋值,只是把范围传过去,然后出队的时候再进行赋值。这样最开始的根节点也无需单独考虑了。

扩展 求中点

前几天和同学发现个有趣的事情,分享一下。

首先假设我们的变量都是 int 值。

二分查找中我们需要根据 startend 求中点,正常情况下加起来除以 2 即可。

int mid = (start + end) / 2

但这样有一个缺点,我们知道int的最大值是 Integer.MAX_VALUE ,也就是2147483647。那么有一个问题,如果 start = 2147483645end = 2147483645,虽然 startend都没有超出最大值,但是如果利用上边的公式,加起来的话就会造成溢出,从而导致mid计算错误。

解决的一个方案就是利用数学上的技巧,我们可以加一个 start 再减一个 start 将公式变形。

(start + end) / 2 = (start + end + start - start) / 2 = start + (end - start) / 2

这样的话,就解决了上边的问题。

然后当时和同学看到jdk源码中,求mid的方法如下

int mid = (start + end) >>> 1

它通过移位实现了除以 2,但。。。这样难道不会导致溢出吗?

首先大家可以补一下 补码 的知识。

其实问题的关键就是这里了>>> ,我们知道还有一种右移是>>。区别在于>>为有符号右移,右移以后最高位保持原来的最高位。而>>>这个右移的话最高位补 0。

所以这里其实利用到了整数的补码形式,最高位其实是符号位,所以当 start + end溢出的时候,其实本质上只是符号位收到了进位,而>>>这个右移可以带着符号位右移,所以之前的信息没有丢掉。

>>有符号右移就会出现问题了,事实上 JDK6 之前都用的>>,这个 BUG 在 java 里竟然隐藏了十年之久。

经过这么多的分析,大家估计体会到了递归的魅力了吧,简洁而优雅。另外的两种迭代的实现,可以让我们更清楚的了解递归到底发生了什么。关于求中点,大家以后就用>>>吧,比start + (end - start) / 2简洁不少,还能给别人科普一下补码的知识。

作者:windliang

来源:https://windliang.cc

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程
  4. JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

    本文著作权归作者所有,如若转载,请注明出处

    转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

    标题:leetcode-108-Convert-Sorted-Array-to-Binary-Search-Tree

    链接:https://www.javajike.com/article/3245.html

« leetcode-107-Binary-Tree-Level-Order-TraversalII
leetcode-109-Convert-Sorted-List-to-Binary-Search-Tree»

相关推荐

QR code