接上一篇《AVL 树旋转及 JS 实现，平衡树支棱起来~》，来了个难的，再来个相对简单的，别一直搁那“旋转树”而打击了“种二叉树”的自信心~~
日拱算法！冲！
题目：
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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 。
- 限制：0 <= 树的结点个数 <= 10000
解题思路：
要验证一颗二叉树是否为平衡二叉树，只需要它的左子树是平衡二叉树，右子树是平衡二叉树，并且左右子树的深度差小于 2；
创建深度计算函数：
检测传入的树，如果为空，返回0，如果不为空，递归调用深度计算函数，分别计算左右子树的深度，将两个深度中的最大值 +1 作为结果返回；
创建平衡判断函数：
使用深度计算函数计算左右子树的深度，计算深度差，递归调用平衡；判断左右子树是否是平衡，如果深度差小于 2，且左右子树都平衡，返回 true，否则返回 false；
/** * 平衡判断函数 */ var isBalanced = function(root) { if(!root){ return true } // 计算左子树和右子树的深度差 // 判断左右子树是否平衡 return Math.abs(depth(root.left) - depth(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right) }; /** * 深度计算函数 */ var depth = function(root) { if(!root) { return 0 } else { // 取左右子树中深度比较大的值作为返回结果 +1 return Math.max(depth(root.left), depth(root.right)) + 1 } }
反过来思考：
上面存在大量的重复计算，还可以使用从下向上的方式：
创建计算深度函数用于深度遍历树：
对左子树和右子树分别递归调用深度函数，计算深度，检测左右子树深度计算的结果，如果左子树的计算结果为 -1，返回 -1，如果右子树的计算结果为 -1，返回 -1，如果左右子树的深度差大于 1，返回 -1，检测通过，执行后续操作；
取左右子树中深度值较大的一个 +1，返回计算结果，调用计算深度函数，计算树，判断计算结果是否为 -1，如果是则二叉树不平衡，如果不是则二叉树平衡；
var isBalanced = function(root) { if(!root){return true} return defs(root) !== -1 }; // 计算树的深度 var defs = function(node) { if(!node) { return 0 } // 计算左子树深度 const left = defs(node.left) // 计算右子树深度 const right = defs(node.right) switch(true) { // 如果左子树为 -1 则返回 -1 case left === -1: return -1 // 如果右子树为 -1 则返回 -1 case right === -1: return -1 // 如果左右子树的深度差大于1 则返回 -1 case Math.abs(left - right) > 1: return -1 default: // 取左右子树中深度较大的值 + 1 返回 return Math.max(left, right) + 1 } }
OK，以上便是本次分享~~
撰文不易，点赞鼓励👍👍👍
我是掘金安东尼，公众号同名，日拱一卒、日掘一金，再会~
