題目
判斷一棵二叉樹是否是平衡二叉樹。（平衡二叉樹每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹的高度差的絕對值不超過1秽之。）
解題方法
- 從根節(jié)點(diǎn)開始政溃，首先判斷其左右子樹高度差的絕對值是否小于等于1，否則直接判定不是平衡二叉樹申鱼；
- 當(dāng)step1中左右子樹高度差的絕對值小于等于1時(shí)捐友，分別判斷左右孩子節(jié)點(diǎn)是否滿足平衡條件匣砖；
- 同樣左右孩子判斷他們的左右子樹高度差猴鲫，然后再繼續(xù)判斷他們的左右孩子節(jié)點(diǎn)拂共，依次遞歸宜狐。
注意：這里不同于之前的遞歸實(shí)現(xiàn)抚恒，之前的遞歸大多只需要獲取依賴的上一步遞歸結(jié)果即可俭驮，這里除了上一步的左右子樹是否平衡的遞歸結(jié)果以外表鳍，還需要判斷自身的左右子樹高度差瓮恭。
代碼
public boolean isBalanced(TreeNode root) {
if(root == null){//空樹為平衡樹
return true;
}
int lh = treeHeight(root.left);//左子樹高
int rh = treeHeight(root.right);//右子樹高
if(Math.abs(lh - rh) > 1){//如果左右子樹高度差絕對值超過1屯蹦，則不平衡
return false;
}
//遞歸判斷節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)是否滿足平衡條件
return isBalanced(root.left) && isBalanced(root.right);
}
//二叉樹樹高
private int treeHeight(TreeNode root){
if(null == root){//空節(jié)點(diǎn)高為0
return 0;
}
int leftHeight = treeHeight(root.left);//左子樹樹高
int rightHeight = treeHeight(root.right);//右子樹樹高
//當(dāng)前節(jié)點(diǎn)高為左右子樹高度最大值加1
return leftHeight >= rightHeight ? (leftHeight + 1) : (rightHeight + 1);
}
