#yyds干货盘点# 解决剑指offer：判断是不是平衡二叉树

2 years ago

source link: https://blog.51cto.com/u_15488507/5410326
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

#yyds干货盘点# 解决剑指offer：判断是不是平衡二叉树

原创

97的风 2022-06-23 09:42:18 博主文章分类：面试题 ©著作权

文章标签 平衡二叉树二叉树子树 文章分类 Java 编程语言 阅读数178

1.简述：

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

样例解释：

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

数据范围：,树上节点的val值满足要求：空间复杂度，时间复杂度

输入描述：

输入一棵二叉树的根节点

返回值描述：

输出一个布尔类型的值

{1,2,3,4,5,6,7}

2.代码实现：

public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null){
return true;
}
int left = deep(root.left);
int right = deep(root.right);
int v = Math.abs(left - right);
if(v > 1){
return false;
}
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}

private int deep(TreeNode root) {
if(root == null){
return 0;
}
return Math.max(deep(root.left), deep(root.right)) + 1;
}
}

Recommend