平衡二叉树

题目描述：

给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

分析：

如果根据左右子树的深度来判断二叉树是否平衡，那么就会存在节点被重复遍历多次的情况。 我们利用后序遍历的方式遍历二叉树，在遍历到某节点的左右子节点时，根据左右子节点的深度判断是否平衡，并得到当前结点的深度，当最后遍历到树的根节点时，也就判断了该树是否平衡。

int dfs(TreeNode root){ if(root==null) return 0; int left=dfs(root.left); if(left<0) return -1; int right=dfs(root.right); if(right<0) return -1; if(Math.abs(left-right)>1) return -1; return Math.max(left,right)+1; } public boolean isBalanced(TreeNode root) { int height=dfs(root); if(height>=0) return true; return false; }