日拱算法之判断平衡二叉树

掘金安东尼

发布于 2022-09-19 10:53:07

2140

发布于 2022-09-19 10:53:07

文章被收录于专栏：掘金安东尼

这是我参与11月更文挑战的第27天，活动详情查看：2021最后一次更文挑战

接上一篇《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 &amp;&amp; isBalanced(root.left) &amp;&amp; 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，以上便是本次分享~~

撰文不易，点赞鼓励👍👍👍