110-平衡二叉树

leetcode ：https://leetcode-cn.com/problems/balanced-binary-tree/

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

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

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

思路：

1、首先判断左子树是不是平衡二叉树 如果不是就退出递归;

2、然后判断右子树是不是平衡二叉树 如果不是就退出递归;

3、计算左右子树最大高度

• 计算高度：每次遍历树，高度都+1

4、判断左右子树的高度差是否大于1

• 大于0，就返回false

js

var isBalanced = function (root) {
  // 记录二叉树是否平衡
  let flag = true;
  const maxDepth = (root) => {
    if (root == null) return 0;
    // 提前返回
    if (!flag) return;
    let leftMaxDepth = maxDepth(root.left);
    let rightMaxDepth = maxDepth(root.right);
    // 如果左右最大深度大于 1，就不是平衡二叉树
    if (Math.abs(rightMaxDepth - leftMaxDepth) > 1) {
      flag = false;
    }
    return 1 + Math.max(leftMaxDepth, rightMaxDepth);
  };
  maxDepth(root);
  return flag;
};