110. Balanced Binary Tree
110. Balanced Binary Tree
题目
Given a binary tree, determine if it is height-balanced.
Example 1:
![](https://assets.leetcode.com/uploads/2020/10/06/balance_1.jpg)
Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2:
![](https://assets.leetcode.com/uploads/2020/10/06/balance_2.jpg)
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3:
Input: root = []
Output: true
Constraints:
- The number of nodes in the tree is in the range
[0, 5000]
. -10^4 <= Node.val <= 10^4
题目大意
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
解题思路
通过递归的方式,对每个节点进行判断,确保它的左右子树高度差不超过 1,并逐层向下判断:
- 对于每个节点,计算其左子树和右子树的高度差。
- 如果某个节点的左右子树的高度差超过 1,则说明以该节点为根的子树不是平衡的,直接返回
false
。 - 如果该节点是平衡的,继续递归检查其左子树和右子树是否平衡。
- 递归的终止条件是遍历到叶子节点,叶子节点是平衡的。
- 如果整棵树的所有节点都满足平衡条件,返回
true
。
代码
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function (root) {
if (!root) {
return true; // 空树是平衡的
}
// 计算树的高度
const getHeight = (node) => {
if (!node) {
return 0;
}
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
};
// 判断以当前节点为根的子树是否平衡
const isNodeBalanced = (node) => {
if (!node) {
return true; // 空子树是平衡的
}
// 计算左右子树的高度差
const heightDiff = Math.abs(getHeight(node.left) - getHeight(node.right));
// 检查当前节点是否平衡,以及其左右子树是否平衡
return (
heightDiff <= 1 && isNodeBalanced(node.left) && isNodeBalanced(node.right)
);
};
// 检查整棵树是否平衡
return isNodeBalanced(root);
};