0110. 平衡二叉树 #
- 标签:树、深度优先搜索、递归
- 难度:简单
题目大意 #
描述:给定一个二叉树的根节点 root
。
要求:判断该二叉树是否是高度平衡的二叉树。
说明:
- 高度平衡二叉树:二叉树中每个节点的左右两个子树的高度差的绝对值不超过 $1$。
- 树中的节点数在范围 $[0, 5000]$ 内。
- $-10^4 \le Node.val \le 10^4$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:递归遍历 #
- 先递归遍历左右子树,判断左右子树是否平衡,再判断以当前节点为根节点的左右子树是否平衡。
- 如果遍历的子树是平衡的,则返回它的高度,否则返回 -1。
- 只要出现不平衡的子树,则该二叉树一定不是平衡二叉树。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$,其中 $n$ 是二叉树的节点数目。
- 空间复杂度:$O(n)$。递归函数需要用到栈空间,栈空间取决于递归深度,最坏情况下递归深度为 $n$,所以空间复杂度为 $O(n)$。