当前位置：首页 > article >正文

学习记录：js算法（四十六）：平衡二叉树

article 2025/2/24 0:54:56

文章目录

- 平衡二叉树
- - 我的思路
  - 网上思路
- 总结

平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树

图一
在这里插入图片描述
图二

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：
输入：root = []
输出：true

我的思路
递归
网上思路

我的思路

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

讲解

isBalanced 函数: 主函数，用于判断是否平衡。
checkBalance 函数: 辅助函数，递归检查每个节点的左右子树高度差。
如果节点为空，返回高度 0。
递归计算左子树和右子树的高度。
如果发现任何子树不平衡，返回 -1。
如果当前节点的左右子树高度差大于 1，也返回 -1。
否则，返回当前节点的高度。

如果 checkBalance 返回值不是 -1，说明树是平衡的。

网上思路

var isBalanced = function (root) {
  if (root == null) return true;
  const depth = (root) => {
    if (root == null) return 0;
    return Math.max(depth(root.left), depth(root.right)) + 1;
  };
  return (
    Math.abs(depth(root.left) - depth(root.right)) < 2 &&
    isBalanced(root.left) &&
    isBalanced(root.right)
  );
};

讲解

函数定义：
定义一个名为 isBalanced 的函数，接受一个参数 root，表示二叉树的根节点。
基准条件：
如果树的根节点为空，返回 true，因为空树被认为是平衡的。
深度计算函数：
定义一个名为 depth 的递归函数，用于计算树的高度。
if (root == null) return 0：如果当前节点为空，返回高度 0。
return Math.max(depth(root.left), depth(root.right)) + 1：递归调用 depth 函数来计算左子树和右子树的高度，取较大值并加 1，以计算当前节点的高度。

平衡性检查:
通过逻辑与运算符 && 来检查以下条件
Math.abs(depth(root.left) - depth(root.right)) < 2：检查当前节点的左右子树高度差是否小于 2。如果高度差大于或等于 2，说明当前节点不平衡。
isBalanced(root.left)：递归检查左子树是否平衡。
isBalanced(root.right)：递归检查右子树是否平衡。