Leetcode No.111

小咪咪 2022-10-31 00:48 170阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]

## JS 自顶向下的判断 ##

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
    /** * @param {TreeNode} root * @return {boolean} */
    var isBalanced = function(root) { 
        if(!root){ 
            return true;
        }
        if(Math.abs(maxDepth(root.left)-maxDepth(root.right))>1){ 
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
        function maxDepth(root){ 
            if(!root){ 
            return 0;
            }
            let left =maxDepth(root.left);
            let right = maxDepth(root.right);
            let max = Math.max(left,right)+1;
            return max;
        }
    };

类似先序遍历，先找最大高度 然后在判断子树的高度符不符合规则，由于每个根节点都要判断，会有重复计算过程。  
时间复杂度Onlogn  
空间复杂度On

## JS 优化——自底向上 ##

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
    /** * @param {TreeNode} root * @return {boolean} */
    var isBalanced = function (root) { 
        return balanced(root) !== -1
    };
    var 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
    }

时间复杂度On  
空间复杂度On

个人理解两个方法中的函数都是自底向上进行求解，但方法一自底向上只求了高度，真正判断是从上至下，而方法二直接从低向上进行判断

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]: /images/20221024/c7fde993675d4afb8451a0c0b7c819af.png