输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3 / 9 20 / 15 7 返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1 / \ 2 2 / \3 3 / 4 4 返回 false 。
限制：
1 <= 树的结点个数 <= 10000
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
运行未通过的一个思路 树相关问题-递归 从根节点向下进入左右子树AB AB若存在子节点，继续向下递归，递归一次深度加一 取左右子树深度相减的绝对值作为评判是否平衡的标准
上述思路存在的问题：
上述的深度与树的高度并不相同，一个节点的高度是左右子树高度的较大值加一，从下向上计算，而深度是从上向下计算，空节点的深度不为0 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isBalanced(TreeNode root) { if(root.left == null && root.right == null) return true; if(getDepth(root) == -1) return false; else return true; } int depth = 0; public int getDepth(TreeNode node) { if(node != null) { if(Math.abs(getDepth(node.left) - getDepth(node.right)) > 1) return -1; return depth++; } } }一个节点n的高度可以由下式计算 h = 0, 此节点左右子树都为空 h = Math.max(h(n.left), h(n.right)) + 1 ,高度为左右子树最大的高度加一
1.自顶向下递归 对于当前节点，首先计算其左右子树的高度，判断高度差是否大于1，再递归的计算其左右子节点的，判断高度差 注意到给定的树节点的范围 时间：总时间复杂度最好为nlogn，最坏为n2 对于每一层，最上层需要遍历所有节点n，接下来是（n - 1）/ 2 * 2， 直到最后一层，也就是各层执行getHeight（）的时间复杂度为n， 二叉树最好情况下(满树)层数为logn，最坏情况下（链式）层数为n 总时间复杂度最好为nlogn，最坏为n2 空间：n, 栈的深度取决于递归的层数，不超过n
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isBalanced(TreeNode root) { if(root == null) return true;//空节点平衡 else //不平衡的三个条件，左右子树高度差大于1，左右子树不平衡 return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } public int getHeight(TreeNode node) { if(node == null) return 0; else return Math.max(getHeight(node.left), getHeight(node.right)) + 1; } }2.自底向上递归（最优） 自顶向下的方法存在重复计算：getHeight被重复调用 获得高度和判断平衡可以放在一起 对于当前节点，先递归的判断其左右子树是否平衡，再判断以这个节点是否平衡 如果一颗子树平衡，那么返回其高度，否则返回 - 1 子树不平衡整个树就不平衡 若左子树不平衡直接返回 -1，不需要再次递归检查右子树
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isBalanced(TreeNode root) { return getHeight(root) != - 1; } public int getHeight(TreeNode root) { if(root == null) return 0; int leftHeight; int rightHeight; if((leftHeight = getHeight(root.left)) == - 1 || (rightHeight = getHeight(root.right)) == - 1 || Math.abs(leftHeight - rightHeight) > 1) return - 1; else return Math.max(leftHeight, rightHeight) + 1; } }