LeetCode第110题 – 平衡二叉树

56 views

题目

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

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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. 兼顾效率,减少无意义的计算,先递归,再求解。


若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第110题 – 平衡二叉树

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud