每日算法：平衡二叉树

本文转载自微信公众号「三分钟学前端」，每日作者sisterAn  。算法转载本文请联系三分钟学前端公众号。平衡

关于树基础看这里：适合初学者的叉树树

给定一个二叉树，判断它是每日否是高度平衡的二叉树。

本题中，算法一棵高度平衡二叉树定义为：

一个二叉树每个节点 的平衡左右两个子树的高度差的绝对值不超过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 ，即每个子树都平衡时，叉树此时二叉树才是每日平衡二叉树

代码实现：

const isBalanced = function (root) {    if(!root) return true   return Math.abs(depth(root.left) - depth(root.right)) <= 1         && isBalanced(root.left)         && isBalanced(root.right) } const depth = function (node) {      if(!node) return -1     return 1 + Math.max(depth(node.left), depth(node.right)) } 

复杂度分析：

时间复杂度：O(nlogn)，计算 depth 存在大量冗余操作 空间复杂度：O(n)

解答二：自底向上(优化)

解题思路： 利用后续遍历二叉树(左右根)，算法从底至顶返回子树最大高度，平衡判定每个子树是不是平衡树 ，如果平衡，则使用它们的高度判断父节点是企商汇否平衡，并计算父节点的高度，如果不平衡，返回 -1 。

遍历比较二叉树每个节点 的左右子树深度：

比较左右子树的深度，若差值大于 1 则返回一个标记 -1 ，表示当前子树不平衡 左右子树有一个不是平衡的，或左右子树差值大于 1 ，则二叉树不平衡 若左右子树平衡，返回当前树的深度(左右子树的服务器托管深度最大值 +1 )

代码实现：

const isBalanced = function (root) {      return balanced(root) !== -1 }; const balanced = function (node) {      if (!node) return 0     const left = balanced(node.left)     const right = balanced(node.right)     if (left === -1 || right === -1 || Math.abs(left - right) > 1) {          return -1     }     return Math.max(left, right) + 1 } 

复杂度分析：

时间复杂度：O(n) 空间复杂度：O(n)

很赞哦!（32）