写点什么

【LeetCode】检查平衡性 Java 题解

用户头像
HQ数字卡
关注
发布于: 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
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】检查平衡性Java题解