题目描述
实现一个函数,检查二叉树是否平衡,平衡的定义如下,对于树中的任意一个结点,其两颗子树的高度差不超过1。
给定指向树根结点的指针TreeNode*
root
,请返回一个bool,代表这棵树是否平衡
这道题目可以采用
后序遍历
的的方式进行递归遍历;
lh
是符合条件的当前节点左子树的深度,
rh
是符合条件的当前节点有字数的深度
每次判断从叶子节点开始,然后根据递归的特性依次往上判断该二叉树是否平衡
代码如下:
public static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public static boolean isBalance(TreeNode root) {
boolean[] res =new boolean[1];
res[0]=true;
int level=1;
getHeight(root,level,res);
return res[0];
}
private static int getHeight(TreeNode root, int level, boolean[] res) {
if(root==null){
return level;
}
int lh =getHeight(root.left, level+1,res);
if(!res[0]){
return level;
}
int rh =getHeight(root.right,level+1,res);
if(!res[0]){
return level;
}
if(Math.abs(lh-rh)>1){
res[0]=false;
}
return Math.max(lh, rh);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)