题目
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
输入： root = [3,9,20,null,null,15,7] 输出： true
题目解析
思路一
我们这里采用递归进行实现，首先确定递归结束条件：为空时结束，其次，找到左子树深度，右子树深度，用递归寻找
1+Math.max(leftDepth,rightDepth),判断返回值是否为-1，是的话结束，否则再去判断绝对值是否小于1， 最后注意调用该函数的返回值为-1则表示false，通过三元表达式判断返回当前的值
/** * @param {TreeNode} root * @return {boolean} */ var isBalanced = function(root) { let getDepth=(node)=>{ if(node==null) return 0; let leftDepth=getDepth(node.left); let rightDepth=getDepth(node.right); if(leftDepth===-1) return -1; if(rightDepth===-1) return -1; if(Math.abs(leftDepth-rightDepth)>1) return -1; return 1+Math.max(leftDepth,rightDepth); } return getDepth(root)===-1?false:true; };
思路二
我们这里依旧采用递归进行实现，我们先立一个flag变量默认为true，只要有一个高度差绝对值大于1，这个flag就会被置为false，在定义一下递归逻辑，如果是空树，高度记为0，如果flag已经false了，那就没必要往下走了，直接退出且返回false，如果没有则通过递归的方式进行计算左子树的高度和计算右子树的高度，如果左右子树的高度差绝对值大于1，flag置为false，最后返回当前子树的高度，在进行调用递归函数，如果走到最后，那么返回当前flag的值即可
/** * @param {TreeNode} root * @return {boolean} */ var isBalanced = function(root) { let flag = true; function dfs(root) { if(!root || !flag) return 0; const left = dfs(root.left); const right = dfs(root.right); if(Math.abs(left - right) > 1) { flag = false; return 0; } return Math.max(left, right) + 1; } dfs(root); return flag; };
