import java.lang.*; public class Solution { public boolean IsBalanced_Solution(TreeNode root) { if(root==null) return true; return Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right) ? true : false; } public int maxDepth (TreeNode root) { // write code here if(root==null) return 0; return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1; } }返回值应该是:
return Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right) ? true : false;
而不是:
return Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1 ? true : false;
要注意一下平衡二叉树(Balanced Binary Tree)的定义:
- 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,
- 并且左右两个子树都是一棵平衡二叉树。
【1,2,3,4,#,#,5,6】就不是平衡二叉树,虽然左右子树高度差为1,但是不满足左右两个子树都是一棵平衡二叉树。