110. 平衡二叉树-day15

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]

思路和算法
只要得到二叉树中的每个子树的高度，即可判断二叉树是否高度平衡。
规定空二叉树的高度是 0，当二叉树非空时，二叉树的高度是从根结点到最深叶结点的路径上的结点数。
在得到二叉树中的每个子树的高度之后，即可判断二叉树中的每个子树是否高度平衡，并判断原始二叉树是否高度平衡。一个二叉树高度平衡，等价于其左子树和右子树的高度差的绝对值不超过 1，且左子树和右子树都高度平衡。
可以使用深度优先搜索实现，从根结点开始遍历每个结点，得到每个子树的高度并判断每个子树是否高度平衡。计算每个子树的高度和判断每个子树是否高度平衡的过程都是递归的过程。
计算每个子树的高度的递归终止条件是当前子树为空，此时高度是 0。对于其余情况，首先计算当前结点的左子树和右子树的高度，然后得到以当前结点为根结点的子树的高度是左子树和右子树的高度中的最大值加 1。
判断每个子树是否高度平衡的的递归终止条件是当前子树为空，此时高度平衡。对于其余情况，根据左子树和右子树的高度差的绝对值是否不超过 1 以及左子树和右子树是否高度平衡判断当前子树是否高度平衡。
`/**

• Definition for a binary tree node.

• public class TreeNode {

• int val;

• TreeNode left;

• TreeNode right;

• TreeNode(int x)

• }
  */
  class Solution {
  public boolean isBalanced(TreeNode root) {
  if(rootnull)
  {
  return true;
  }
  if(root.left == null && root.rightnull)
  return true;
  if(Math.abs(treeHeight(root.left) - treeHeight(root.right)) > 1)
  return false;
  return isBalanced(root.left) && isBalanced(root.right);

  }

  public int treeHeight(TreeNode root) {
  if(root==null)
  return 0;
  int lh = treeHeight(root.left) +1;
  int rh = treeHeight(root.right) +1;
  return lh > rh ? lh: rh;
  }
  }
  /@一经多少年 你这样写的话，就没有办法判断其子树是否平衡了。 举个例子：如果说根节点的左右子树是平衡的，但是以其左孩子为根的子树是不平衡的，那么这棵树也不是平衡树。
  但是以你这种写法判断的话，在判断完根节点的左右子树后，就返回true了，也就没有办法继续递归判断其左右子树的子树的平衡情况。/`