Lstmxx的空间

110. 平衡二叉树

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

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

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

链接

function isBalanced(root: TreeNode | null): boolean {
  if (root === null) return true
  return traverse(root) >= 0
};

function traverse(root: TreeNode): number {
  if (root === null) return 0
  const leftDep = traverse(root.left)
  const rightDep = traverse(root.right)
  if (leftDep == -1 || rightDep == -1 || Math.abs(leftDep - rightDep) > 1) {
    return -1;
  } else {
    return Math.max(leftDep, rightDep) + 1;
  }
}