后序遍历,当不满足返回-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; }