110.平衡二叉树

链接：110.平衡二叉树
难度：Easy
标签：树、深度优先搜索、二叉树
简介：给定一个二叉树，判断它是否是高度平衡的二叉树。

题解 1 - typescript

• 编辑时间：2020-08-17
• 执行用时：112ms
• 内存消耗：44.4MB
• 编程语言：typescript
• 解法介绍：计算子树是否平衡，以及该树是否平衡。

const map = new Map<TreeNode, number>();
function isBalanced(root: TreeNode | null): boolean {
  if (root === null) return true;
  const h = (node: TreeNode | null): number => {
    if (node === null) return 0;
    if (map.has(node)) return map.get(node)!;
    const height = 1 + Math.max(h(node.left), h(node.right));
    map.set(node, height);
    return height;
  };
  return (
    isBalanced(root.left) && isBalanced(root.right) && Math.abs(h(root.left) - h(root.right)) <= 1
  );
}

题解 2 - c

• 编辑时间：2021-11-27
• 执行用时：4ms
• 内存消耗：8.7MB
• 编程语言：c
• 解法介绍：递归。

// 判断节点是否平衡,不平衡返回-1,平衡返回高度
int _isBalanced(struct TreeNode *node) {
    if (!node) return 0;
    int l = _isBalanced(node->left), r = _isBalanced(node->right);
    if (l == -1 || r == -1) return -1;
    if (abs(l - r) <= 1) return (l > r ? l : r) + 1;
    return -1;
}
bool isBalanced(struct TreeNode* root){
    return _isBalanced(root) > -1;
}