剑指offer55-Ⅱ 平衡二叉树【DFS】
题目描述
输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
1 | 3 |
返回 true
。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1 | 1 |
返回 false
。
限制:
0 <= 树的结点个数 <= 10000
解题思路
方法一:深度优先搜索
dfs方法,后序遍历,计算出左右子树的长度,判断左右子树的高度差的绝对值是否小于1,即判断是否为平衡二叉树,递归。
代码实现
1 | // -1为不平衡状态,平衡状态下返回树的高度 |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n) 递归栈
资料
剑指offer55-Ⅱ 平衡二叉树【DFS】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.