问题

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:
给定二叉树 [3,9,20,null,null,15,7] 

  1.    3
  2.   / \
  3.  9  20
  4.    /  \
  5.   15   7

返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]

  1.       1
  2.      / \
  3.     2   2
  4.    / \
  5.   3   3
  6.  / \
  7. 4   4

返回 false 。
限制：
1 <= 树的结点个数 <= 10000。

解答

采用剪枝法（最佳解答）。
利用二叉树的后序遍历，获取到左右子树的高度，如果左右子树的高度相差大于1时，则该树不时平衡二叉树，返回 -1， 相当于剪枝，后面递归中判断到左右子树返回的是-1，则同样直接返回 -1。如果左右子树的高度小于1，则返回当前子树的高度，也就是左右子树中高度最高的那颗树的高度 + 1。
算法流程：
postRecursion() :
返回值：

  • 当左右子树的高度大于1时，返回 -1，当左右子树的高度小于等于1，返回当前子树的高度，即左右子树中高度最高的高度 +1。
  • 当当前子树的为 null 时，表明已经越过叶子节点，返回 0 ```java class Solution {
    public boolean isBalanced(TreeNode root) { int res = order(root); return res == -1 ? false : true; } private int postRecursion(TreeNode node){ if(node == null){
    1.    return  0;
    } int left = order(node.left); if(left == -1 )
       return -1;
    int right = order(node.right); if(right == -1)
       return -1;
    // 判断左右子树的高度是否大于1 if(Math.abs(left - right) > 1)
       return -1;
    return left > right? left + 1 : right + 1; }

} ```