LeetCode第110题 – 平衡二叉树

题目

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

解答

	/**
	 * 辅助方法，用于计算当前树节点的高度。
	 * @param node 树节点
	 * @return 高度
	 */
	public int depth(TreeNode node) {
		if (node == null) {
			return 0;
		}

		int left = depth(node.left);
		int right = depth(node.right);
		return Math.max(left, right) + 1;
	}
	/**
	 * 按照题目要求，检查当前节点是否平衡。
	 * @param root 树节点
	 * @return true表示平衡
	 */
	public boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		}

		if (!isBalanced(root.left) || !isBalanced(root.right)) {
			return false;
		}

		int left = depth(root.left);
		int right = depth(root.right);
		if (Math.abs(left - right) > 1) {
			return false;
		}

		return true;
	}

要点

注意点：基于树的特点，使用递归方法来求解。

1. 题目中对平衡二叉树的定义，要求计算给定节点的高度。
2. 检查给定节点左、右子树的高度之差，是否在1以内。
3. 兼顾效率，减少无意义的计算，先递归，再求解。