前言：
当前兄弟们对“平衡二叉树的实现”可能比较珍视，各位老铁们都想要学习一些“平衡二叉树的实现”的相关资讯。那么小编也在网摘上网罗了一些对于“平衡二叉树的实现””的相关资讯，希望咱们能喜欢，大家快快来了解一下吧！题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例
输入：
3 / \9 20 / \ 15 7
输出：
true写在前面
本文答案参考自 LeetCode 官方题解。
解法1：自顶向下的递归
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
则我们可以递归地计算每个节点的左右两个子树的高度差。
其中，计算一个节点的高度则又是一个递归函数。[思考]
代码
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; } }}作者：LeetCode-Solution链接：来源：力扣（LeetCode）解法2：自底向上的递归【解法1】中写了两个递归函数，效率不太高。
所以我们可以尝试自底向上的递归，具体思路是：
定义跟【解法1代码】中相似的 height() 函数，递归地往下走，在函数返回前计算并判断当前节点的左右子树的高度差根据计算结果返回-1（表示false）或当前节点高度代码
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; } }}作者：LeetCode-Solution链接：来源：力扣（LeetCode） 版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #平衡二叉树的实现 #理想平衡树和平衡二叉树
