平衡二叉树

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

图一

图二

示例 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;
};

讲解

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

讲解

1. 函数定义：
   定义一个名为 isBalanced 的函数，接受一个参数 root，表示二叉树的根节点。
2. 基准条件：
   如果树的根节点为空，返回 true，因为空树被认为是平衡的。
3. 深度计算函数：
   • 定义一个名为 depth 的递归函数，用于计算树的高度。
   • if (root == null) return 0： 如果当前节点为空，返回高度 0。
   • return Math.max(depth(root.left), depth(root.right)) + 1：递归调用 depth 函数来计算左子树和右子树的高度，取较大值并加 1，以计算当前节点的高度。
4. 平衡性检查:
   通过逻辑与运算符 && 来检查以下条件
   • Math.abs(depth(root.left) - depth(root.right)) < 2：检查当前节点的左右子树高度差是否小于 2。如果高度差大于或等于 2，说明当前节点不平衡。
   • isBalanced(root.left)：递归检查左子树是否平衡。
   • isBalanced(root.right)： 递归检查右子树是否平衡。

总结

递归好用