JZ79 判断是不是平衡二叉树
描述
输入一棵节点数为 n 二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
思路
左右两个子树的高度差的绝对值不超过1
左右两个子树都是一棵平衡二叉树
代码
package esay.JZ79判断是不是平衡二叉树;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
//自顶向下
/*public boolean IsBalanced_Solution(TreeNode root) {
//空树也是平衡二叉树
if (root == null) return true;
//左子树深度
int left = deep(root.left);
//右子树深度
int right = deep(root.right);
if (left - right > 1 || right - left > 1) return false;
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
public int deep (TreeNode node) {
if (node == null) return 0;
//左遍历
int left = deep(node.left);
//右遍历
int right = deep(node.right);
return left > right ? left + 1 :right + 1;
}*/
//自底向上
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null) return true;
return getdepth(root) != -1;
}
public int getdepth (TreeNode node) {
if (node == null) return 0;
//左遍历
int left = getdepth(node.left);
if (left < 0) return -1;
//右遍历
int right = getdepth(node.right);
if (right < 0) return -1;
return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
}
}
hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 »
每日算法之判断是不是平衡二叉树