题目描述
输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
plaintext
1 | 3 |
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
plaintext
1 | 1 |
返回 false 。
限制:
- 0<=树的结点个数<=10000
注意:本题与主站 110 题相同:https://leetcode-cn.com/problems/balanced-binary-tree/
算法 1
(DFS,递归) O(n)
这道题目其实就是在求二叉树中的每个节点最大深度(高度)的过程中判断以当前节点为根的树是否为二叉平衡树。
定义一个全局答案,首先假设是平衡二叉树,递归后序遍历二叉树,遍历的过程中如果遇到不是平衡二叉树的节点,说明整棵二叉树就不是平衡二叉树。
时间复杂度
二叉树的每个节点只会被遍历一次,所以时间复杂度为 O(n)。
空间复杂度
O(logn),最坏情况下 O(n)。
C++ 代码
cpp
1 | /** |
算法 2
(BFS,迭代) O(n2)
首先使用层序遍历 BFS 写一个求节点高度的函数。
迭代法前序遍历二叉树,对于每个节点判断它的左子树和右子树的高度之差绝对值是否大于 1,如果大于 1 说明不是平衡二叉树,否则当所有节点遍历完成后,说明该树是一棵平衡二叉树。
时间复杂度
求二叉树的高度所需的时间为 O(n),每个节点都需要求一次高度,所以时间复杂度为 O(n2)。
空间复杂度
最坏情况下每次求二叉树的高度所需系统栈空间为 O(n)。
C++ 代码
cpp
1 | /** |