后序遍历,当不满足返回-1
平衡二叉树
http://www.nowcoder.com/questionTerminal/8b3b95850edb4115918ecebdf1b4d222
减少重复访问,后续遍历,当Math.abs(left-right)>1,则直接返回-1.最后平衡判断 recur(root)!=-1。
/**
* 输入一棵二叉树,判断该二叉树是否是平衡二叉树。
* @param root 二叉树
* @return 判断该二叉树是否是平衡二叉树。
*/
public boolean IsBalanced_Solution(TreeNode root) {
return BalancedRecur(root)!=-1;
}
public int BalancedRecur(TreeNode root){
if(root==null){
return 0;
}
int left=BalancedRecur(root.left);
if(left==-1) return -1;
int right=BalancedRecur(root.right);
if(right==-1){
return -1;
}
return Math.abs(left-right)<=1?Math.max(left,right)+1:-1;
} 

查看14道真题和解析