leetcode110：平衡二叉树 #44

Activity

1. sisterAn

   added

   LeetCode

   剑指Offer

   on May 18, 2020
2. plane-hjh commented on May 19, 2020

   

   plane-hjh

   on May 19, 2020

   Last edited by plane-hjh

   More actions

   思路：后序遍历，使用递归计算节点的高度

   1. 比较左右子树的深度，若差值大于1 则返回一个标记 -1表示当前子树不平衡

   2. 左右子树有一个不是平衡的，或左右子树差值大于1，则整课树不平衡

   3. 若左右子树平衡，返回当前树的深度（左右子树的深度最大值+1）

   /**
    * Definition for a binary tree node.
    * function TreeNode(val) {
    *     this.val = val;
    *     this.left = this.right = null;
    * }
    */
   /**
    * @param {TreeNode} root
    * @return {boolean}
    */
   var isBalanced = function (root) {
     function balanced(node) {
       // 递归的基线条件
       if (!node) return 0;
   
       // 后序遍历
       const left = balanced(node.left);
       const right = balanced(node.right);
   
       if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1;
   
       // 从底层的0开始，每一层+1之后往外抛
       return Math.max(left, right) + 1;
     }
   
     return balanced(root) !== -1
   };
3. luweiCN commented on May 19, 2020

   

   luweiCN

   on May 19, 2020

   More actions

   var treeHeight = function (root) {
     if (root === null) return 0;
     return Math.max(treeHeight(root.left), treeHeight(root.right)) + 1;
   };
   
   /**
    * @param {TreeNode} root
    * @return {boolean}
    */
   var isBalanced = function (root) {
     if (root === null) return true;
     let leftHeight = treeHeight(root.left);
     let rightHeight = treeHeight(root.right);
     if (Math.abs(leftHeight - rightHeight) > 1) {
       return false;
     } else {
       return isBalanced(root.left) && isBalanced(root.right);
     }
   };
4. 13001920223 commented on May 19, 2020

   

   13001920223

   on May 19, 2020

   More actions

   解题思路

   · 定义height方法获取二叉树最大深度

   · 获取子树高度，如果差值大于一则不是平衡二叉树返回false

   · 递归调用直到遍历完成

   var isBalanced = function(root) {
       if (!root) { // 如果没有值直接返回true
           return true
       }
       if (Math.abs(height(root.left) - height(root.right)) > 1) { // 判断差值是否大于1
           return false
       }
       return isBalanced(root.left) && isBalanced(root.right); // 递归调用子树
   };
   function height(root) { // 获取子树最大深度
       if (!root) {
           return 0
       }
       return Math.max(height(root.left), height(root.right)) + 1;
   }
5. sisterAn commented on May 19, 2020

   

   sisterAn

   on May 19, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解答一：自顶向下（暴力法）

   解题思路： 自顶向下的比较每个节点的左右子树的最大高度差，如果二叉树中每个节点的左右子树最大高度差小于等于 1 ，即每个子树都平衡时，此时二叉树才是平衡二叉树

   代码实现：

   const isBalanced = function (root) {
     if(!root) return true
     return Math.abs(depth(root.left) - depth(root.right)) <= 1
           && isBalanced(root.left)
           && isBalanced(root.right)
   }
   const depth = function (node) {
       if(!node) return -1
       return 1 + Math.max(depth(node.left), depth(node.right))
   }

   复杂度分析：

   • 时间复杂度：O(nlogn)，计算 depth 存在大量冗余操作
   • 空间复杂度：O(n)

   解答二：自底向上（优化）

   解题思路： 利用后续遍历二叉树（左右根），从底至顶返回子树最大高度，判定每个子树是不是平衡树 ，如果平衡，则使用它们的高度判断父节点是否平衡，并计算父节点的高度，如果不平衡，返回 -1 。

   遍历比较二叉树每个节点 的左右子树深度：

   • 比较左右子树的深度，若差值大于 1 则返回一个标记 -1 ，表示当前子树不平衡
   • 左右子树有一个不是平衡的，或左右子树差值大于 1 ，则二叉树不平衡
   • 若左右子树平衡，返回当前树的深度（左右子树的深度最大值 +1 ）

   代码实现：

   const isBalanced = function (root) {
       return balanced(root) !== -1
   };
   const balanced = function (node) {
       if (!node) return 0
       const left = balanced(node.left)
       const right = balanced(node.right)
       if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
           return -1
       }
       return Math.max(left, right) + 1
   }

   复杂度分析：

   • 时间复杂度：O(n)
   • 空间复杂度：O(n)

   leetcode

   👍React with 👍3Reacted by Aaron Sprinkle, 瓶子君 and JohnApache
6. AnranS commented on Nov 20, 2020

   

   AnranS

   on Nov 20, 2020

   More actions

   var isBalanced = function(root) {
       function help(root) {
           if(root === null) return 0;
           const left = help(root.left);
           const right = help(root.right);
           if(left === -1 || right === -1 || Math.abs(left - right) > 1) return -1;
           return Math.max(left, right) + 1;
       }
       return help(root) !== -1;
   };