1.leetcode原题链接:. - 力扣(LeetCode)
2.题目描述
给定一个二叉树,判断它是否是
平衡二叉树
示例 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]
内 -104 <= Node.val <= 104
3.实现方法
方法一:自顶向下
从根节点开始,自顶向下递归地判断左右子树是否平衡,先分别计算当前节点左右子树的高度,如果高度差不超过1,那么再递归地分别判断左右子树。
class Solution {
public boolean isBalanced(TreeNode root) {
if ( root == null ) return true;
return Math.abs( height(root.left) - height(root.right) ) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}
// 定义一个height方法,用于计算树的高度
public int height(TreeNode root){
if ( root == null ) return 0;
return Math.max( height(root.left), height(root.right) ) + 1;
}
}
方法二:自底向上
自底向上地遍历节点进行判断。计算每个节点的高度时,需要递归地处理左右子树;所以可以先判断左右子树是否平衡,计算出左右子树的高度,再判断当前节点是否平衡。这样,计算高度的方法height,对于每个节点就只调用一次了。
class Solution {
public boolean isBalanced(TreeNode root) {
if ( root == null ) return true;
int leftHeight = balancedHeight(root.left);
int rightHeight = balancedHeight(root.right);
return leftHeight != -1 && rightHeight != -1 && Math.abs( leftHeight - rightHeight ) <= 1;
}
// 定义一个height方法
public int balancedHeight(TreeNode root){
if ( root == null ) return 0;
int leftHeight = balancedHeight(root.left);
int rightHeight = balancedHeight(root.right);
// 如果子树不平衡,直接返回-1
if ( leftHeight == -1 || rightHeight == -1 || Math.abs( leftHeight - rightHeight ) > 1)
return -1;
// 如果平衡,高度就是左右子树高度最大值,再加1
return Math.max( leftHeight, rightHeight ) + 1;
}
}