【LeetCode】检查平衡性 Java 题解

关注

发布于: 7 小时前

题目描述

实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

示例 1:给定二叉树 [3,9,20,null,null,15,7]    3   / \  9  20    /  \   15   7返回 true 。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/check-balance-lcci著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的每日一题是二叉树的平衡性题目。题意指出了平衡性的定义。任意一个节点，其两棵子树的高度差不超过 1。
首先，我们需要解决如何求树的高度？当树为 null 的时候，高度是 0。二叉树的高度，是左子树和右子树的最大高度 +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) {        if (root == null) {            return true;        } else {            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);        }    }
    public int height(TreeNode root) {        if (root == null) {            return 0;        } else {            return Math.max(height(root.left), height(root.right)) + 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 height(root) >= 0;    }
    public int height(TreeNode root) {        if (root == null) {            return 0;        }        int leftHeight = height(root.left);        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {            return -1;        } else {            return Math.max(leftHeight, rightHeight) + 1;        }    }}

复制代码

总结

自顶向下解法的时间复杂度是 O(n * n), 空间复杂度是 O(n)
自底向上解法的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持算法每日一题，加油！

发布于: 7 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/92a9c3e2a932e72f22f841c98】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】检查平衡性 Java 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论