110. Balanced Binary Tree

🟢   🔖  树 深度优先搜索 二叉树  🔗 LeetCode

题目

Given a binary tree, determine if it is height-balanced.

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: true

Example 2:

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. 对于每个节点，计算其左子树和右子树的高度差。
2. 如果某个节点的左右子树的高度差超过 1，则说明以该节点为根的子树不是平衡的，直接返回 false。
3. 如果该节点是平衡的，继续递归检查其左子树和右子树是否平衡。
4. 递归的终止条件是遍历到叶子节点，叶子节点是平衡的。
5. 如果整棵树的所有节点都满足平衡条件，返回 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);
};

相关题目

相关题目

• 104. 二叉树的最大深度

- [104. 二叉树的最大深度](./0104.md)