LC 110.平衡二叉树

110. 平衡二叉树

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

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

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

示例 1：

输入： root = [3,9,20,null,null,15,7]
输出： true

示例 2：

输入： root = [1,2,2,3,3,null,null,4,4]
输出： false

示例 3：

输入： root = []
输出： true

提示：

• 树中的节点数在范围 [0, 5000] 内
• $-10^4\le Node.val\le 10^4$

解法一(后序遍历+递归)

思路分析：

1. 使用后序遍历，先遍历左右节点获取高度进行判断；

2. 若左右子树高度差值不超过1，则符合条件；

3. 如超过1，则不符合条件，返回false；

4. 通过递归的方式求取左右子树的深度

实现代码如下：

class Solution {
    public boolean isBalanced(TreeNode root) {
		if (root == null) return true;
		// 后序遍历 先遍历获取左右子树高度
		int leftHeight = getHeight(root.left);
		int rightHeight = getHeight(root.right);
		return Math.abs(leftHeight - rightHeight) <= 1
				&& isBalanced(root.left) && isBalanced(root.right);
    }
	// 后序遍历获取 二叉树高度
	private int getHeight(TreeNode node) {
		if (node == null)
			return 0;
		return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
	}
}

提交结果如下：

解答成功:
执行耗时:1 ms,击败了43.88% 的Java用户
内存消耗:43.2 MB,击败了10.39% 的Java用户

复杂度分析：

• 时间复杂度：$O(n^2)$，遍历二叉树结点时，需要遍历求取二叉树结点的高度

• 空间复杂度：不考虑递归消耗，$O(1)$

解法二(优化解法一)

思路分析：

1. 首先对于解法一进行思考，每次判断一个结点的左右子节点是否符合要求时，需要再去求左右结点的高度，这种判断是从上向下的，对于下面的一些结点会重复访问多次，时间复杂度过高。

2. 因此可以考虑使用自下向上的判断二叉树是否为高度平衡二叉树，即获取子树高度并判断，然后向上接着判断

3. 若判断子树为平衡，则返回该子树高度，若不平衡则返回-1

实现代码如下：

class Solution {
	public boolean isBalanced(TreeNode root) {
		if (root == null) return true;
		return getHeight(root) >= 0;
	}
	// 后序遍历获取 二叉树高度
	private int getHeight(TreeNode node) {
		if (node == null)
			return 0;
		// 左
		int leftHeight = getHeight(node.left);
		// 右
		int rightHeight = getHeight(node.right);
		if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight-rightHeight) > 1)
			return -1;	// 若左子树或右子树或当前子树不平衡 则返回-1
		// 若当前子树平衡 则返回其高度
		return Math.max(leftHeight, rightHeight) + 1;
	}
}

提交结果如下：

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:43.2 MB,击败了10.39% 的Java用户

复杂度分析：

• 时间复杂度：$O(n)$，自下向上只需遍历一遍二叉树

• 空间复杂度：$O(n)$，考虑递归二叉树的层数，对空间的消耗