【LeetCode】检查平衡性 Java 题解
题目描述
实现一个函数,检查二叉树是否平衡。在这个问题中,平衡树的定义如下:任意一个节点,其两棵子树的高度差不超过 1。
复制代码
思路分析
今天的每日一题是二叉树的平衡性题目。题意指出了平衡性的定义。任意一个节点,其两棵子树的高度 差不超过 1。
首先,我们需要解决如何求树的高度?当树为 null 的时候,高度是 0。二叉树的高度,是左子树和右子树的最大高度 +1。
这个题目首先可以实用自顶向下的思想求解,每个节点都比较计算节点的高度。
观察自顶向下的算法,发现有很多的重复计算,时间复杂度高。
针对重复计算,我们可以采用自底向上的思想求解,提升执行效率。参考代码如下:
通过代码
自顶向下思想求解。
复制代码
自底向上思想求解
复制代码
总结
自顶向下解法的时间复杂度是 O(n * n), 空间复杂度是 O(n)
自底向上解法的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/92a9c3e2a932e72f22f841c98】。文章转载请联系作者。
评论