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]
  • − 1 0 4 ≤ N o d e . v a l ≤ 1 0 4 -10^4 \leq Node.val \leq 10^4 104Node.val104

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

思路分析:

  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(n^2) O(n2),遍历二叉树结点时,需要遍历求取二叉树结点的高度

  • 空间复杂度:不考虑递归消耗, O ( 1 ) O(1) 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) O(n),自下向上只需遍历一遍二叉树

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

相关推荐

  1. 110.平衡

    2024-04-03 09:38:03       3 阅读
  2. [leetcode] 110. 平衡

    2024-04-03 09:38:03       4 阅读

最近更新

  1. 从0开始深入理解Spring(1)--SpringApplication构造

    2024-04-03 09:38:03       0 阅读
  2. kubeadm 升级 k8s集群 1.17到1.20

    2024-04-03 09:38:03       0 阅读
  3. SpringCloudAlibaba+RocketMQ实现对消息中间件的整合

    2024-04-03 09:38:03       0 阅读
  4. Docker中Kafka容器创建/更新Topic支持多分区

    2024-04-03 09:38:03       0 阅读
  5. WPF-关于动画Animation(及其常见问题)

    2024-04-03 09:38:03       0 阅读
  6. Flask RESTful视图使用(蓝图、装饰器、渲染模板)

    2024-04-03 09:38:03       0 阅读
  7. 三个目前主流的计算机视觉软件

    2024-04-03 09:38:03       0 阅读

热门阅读

  1. 菜鸟笔记-Python函数-ones

    2024-04-03 09:38:03       5 阅读
  2. 14、Lua 模块与包

    2024-04-03 09:38:03       2 阅读
  3. 基于单片机的LED 灯调光系统的研究

    2024-04-03 09:38:03       3 阅读
  4. Git 多人协作开发

    2024-04-03 09:38:03       4 阅读
  5. Springboot自动配置原理

    2024-04-03 09:38:03       4 阅读
  6. JVM原理

    2024-04-03 09:38:03       2 阅读
  7. whisper-v3模型部署环境执行

    2024-04-03 09:38:03       2 阅读
  8. HTML/XML转义字符对照

    2024-04-03 09:38:03       4 阅读