平衡二叉树（ LeetCode 110 ）
一、题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 平衡二叉树（ LeetCode 110 ）:https://leetcode-cn.com/problems/balanced-binary-tree
class Solution {
public boolean isBalanced(TreeNode root) {
// 自底向上判断，只要返现有叶子树出现非平衡二叉树的情况，那么就是不是平衡二叉树了
return recur(root) != -1;
}
private int recur(TreeNode curNode) {
// 递归终止条件
// 如果当前节点 curNode 为空，那么高度就是 0
if (curNode == null) return 0;
// 递归的计算当前节点 curNode 的左子树高度
int left = recur(curNode.left);
// 如果发现为 -1，即表示左子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
// 提前终止了后续的判断
if(left == -1) return -1;
// 递归的计算当前节点 curNode 的右子树高度
int right = recur(curNode.right);
// 如果发现为 -1，即表示右子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
// 提前终止了后续的判断
if(right == -1) return -1;
// 1、否则说明在 curNode 的左子树中没有发现不是平衡二叉树的情况
// 2、否则说明在 curNode 的右子树中没有发现不是平衡二叉树的情况
// 因此计算一下当前节点 curNode 是否是平衡二叉树
// 即计算 curNode 的左子树高度与右子树高度差
// 如果发现小于 2，那么返回以当前节点 curNode 为根节点的子树的最大高度
// 即节点 curNode 的左右子树中最大高度加 1
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 平衡二叉树（ LeetCode 110 ）:https://leetcode-cn.com/problems/balanced-binary-tree
class Solution {
public:
bool isBalanced(TreeNode* root) {
// 自底向上判断，只要返现有叶子树出现非平衡二叉树的情况，那么就是不是平衡二叉树了
return recur(root) != -1;
}
private:
int recur(TreeNode* curNode) {
// 递归终止条件
// 如果当前节点 curNode 为空，那么高度就是 0
if (curNode == NULL) return 0;
// 递归的计算当前节点 curNode 的左子树高度
int left = recur(curNode->left);
// 如果发现为 -1，即表示左子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
// 提前终止了后续的判断
if(left == -1) return -1;
// 递归的计算当前节点 curNode 的右子树高度
int right = recur(curNode->right);
// 如果发现为 -1，即表示右子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
// 提前终止了后续的判断
if(right == -1) return -1;
// 1、否则说明在 curNode 的左子树中没有发现不是平衡二叉树的情况
// 2、否则说明在 curNode 的右子树中没有发现不是平衡二叉树的情况
// 因此计算一下当前节点 curNode 是否是平衡二叉树
// 即计算 curNode 的左子树高度与右子树高度差
// 如果发现小于 2，那么返回以当前节点 curNode 为根节点的子树的最大高度
// 即节点 curNode 的左右子树中最大高度加 1
return abs(left - right) < 2 ? max(left, right) + 1 : -1;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 平衡二叉树（ LeetCode 110 ）:https://leetcode-cn.com/problems/balanced-binary-tree
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
# 自底向上判断，只要返现有叶子树出现非平衡二叉树的情况，那么就是不是平衡二叉树了
return self.recur(root) != -1
def recur(self, curNode: TreeNode):
# 递归终止条件
# 如果当前节点 curNode 为空，那么高度就是 0
if not curNode : return 0
# 递归的计算当前节点 curNode 的左子树高度
left = self.recur(curNode.left)
# 如果发现为 -1，即表示左子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
# 提前终止了后续的判断
if left == -1 : return -1
# 递归的计算当前节点 curNode 的右子树高度
right = self.recur(curNode.right)
# 如果发现为 -1，即表示右子树中出现了高度差大于 2 的情况，已经不是平衡二叉树了，可以直接返回这个结果给上层
# 提前终止了后续的判断
if right == -1 : return -1
# 1、否则说明在 curNode 的左子树中没有发现不是平衡二叉树的情况
# 2、否则说明在 curNode 的右子树中没有发现不是平衡二叉树的情况
# 因此计算一下当前节点 curNode 是否是平衡二叉树
# 即计算 curNode 的左子树高度与右子树高度差
# 如果发现小于 2，那么返回以当前节点 curNode 为根节点的子树的最大高度
# 即节点 curNode 的左右子树中最大高度加 1
return max(left, right) + 1 if abs(left - right) < 2 else -1
