本文转载自微信公众号《三分钟学前端》，作者安姐。转载本文请联系三分钟学习前端公众号。有关树的基础知识，请参见此处：初学者树给定一棵二叉树，确定它是否是高度平衡的二叉树。本题对一棵高度平衡二叉树的定义为：一棵二叉树每个节点的左右子树高度差的绝对值不超过1。例1：给定一棵二叉树[3,9,20,null,null,15,7]3/\920/\157返回true。示例2：给定二叉树[1,2,2,3,3,null,null,4,4]1/\22/\33/\44返回false。答案一：自上而下（暴力法）解题思路：自上而下比较每个节点左右子树的最大高度差，如果在二叉树小于等于1，即当每个子树都平衡时，二叉树就是平衡二叉树代码实现：constisBalanced=function(root){if(!root)returntruereturnMath.abs(depth(root.left)-depth(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right)}constdepth=function(node){if(!node)return-1return1+Math.max(depth(node.left),depth(node.right))}复杂度分析：时间复杂度：O(nlogn)，计算深度有很多冗余操作空间复杂度：O(n)方案二：自下而上（优化）解题思路：利用后续遍历二叉树（左右根），从底部返回子树的最大高度到顶部，判断是否e每个子树都是一棵平衡树。如果平衡，则用它们的高度判断父节点是否平衡，并计算父节点的高度。如果不平衡，返回-1。遍历并比较二叉树每个节点的左右子树深度：比较左右子树的深度，如果差值大于1，则返回标记-1，表示当前子树不平衡并且左右子树之一不平衡，或者左右子树不平衡如果差值大于1，则二叉树不平衡。如果左右子树平衡，则返回当前树的深度（左右子树的最大深度+1）。代码实现：constisBalanced=function(root){returnbalanced(root)!==-1};constbalanced=function(node){if(!node)return0constleft=balanced(node.left)constright=balanced(node.right)if(left===-1||right===-1||Math.abs(left-right)>1){return-1}returnMath.max(left,right)+1}复杂度分析：时间复杂度：O(n)空间复杂度：O(n)
