难度：简单

题目描述：
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例：
image.png

解题思路：

自顶向下

  • 核心思想前序遍历(先当前，后子结点)
  • 递归法-有大量重复
  • 自顶向下，求左右高度，计算差值
    1. var isBalanced = function (root) {
    2.   if (!root) {
    3.       return true;
    4.   }
    5.   /** 递归法-有大量重复
    6.    * 1. 自顶向下，求左右高度，计算差值
    7.    */
    8.   let leftHeight = getNodeHeight(root.left);
    9.   let rightHeight = getNodeHeight(root.right);
    10.   if (Math.abs(leftHeight - rightHeight) > 1) {
    11.       return false;
    12.   }
    13.   return isBalanced(root.left) && isBalanced(root.right);
    14. };
    15. function getNodeHeight(node) {
    16.   if (!node) {
    17.       //没有了返回0,不表示不稳定
    18.       return 0
    19.   }
    20.   return Math.max(getNodeHeight(node.left), getNodeHeight(node.right)) + 1;
    21. }

自底向上
核心思想后序遍历(先子结点，后当前)
从叶子节点向上，-1表示不平衡,>0表示高度
比较左右节点高度，是否满足avl(有一边是-1，则直接返回-1)，不满足-1，否则返回节点的高度
最后看高度是-1还是其它的

  1. var isBalanced = function (root) {
  2.     if (!root) {
  3.         return true;
  4.     }
  5.     /** 思路
  6.      * 1. 从叶子节点向下，-1表示不平衡,>0表示高度
  7.      * 2. 比较左右节点高度，是否满足avl，不满足-1，否则返回节点的高度
  8.      * 3. 最后看高度是-1还是其它的
  9.      */
  10.     return balancedHelper(root) > -1;
  11. };
  12. function balancedHelper(node) {
  13.     if (!node) {
  14.         //没有了返回0,不表示不稳定
  15.         return 0
  16.     }
  17.     let leftHeight = balancedHelper(node.left);
  18.     let rightHeight = balancedHelper(node.right);
  19.     //如果有一边是-1，则表明不平衡
  20.     if (leftHeight == -1 || rightHeight == -1) {
  21.         return -1;
  22.     }
  23.     //如果差值大于1,返回-1
  24.     if (Math.abs(leftHeight - rightHeight) > 1) {
  25.         return -1;
  26.     }
  27.     //如果都不是-1，将左、右最大height+当前返回
  28.     return Math.max(leftHeight, rightHeight) + 1;
  29. }