【leetcode热题】平衡二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了【leetcode热题】平衡二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

难度：简单
通过率： 39.9%
题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目描述

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

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

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

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

解法：

这个问题可以递归地去检查子树的是否平衡，深度的计算应该是从树的叶子开始，然后复用子树的求得的深度一些解法，直接去求子树的深度，但是没有复用深度，造成了很多没必要的计算。

这里一个困难点在于，如何在计算深度的同时，向外层传递不平衡的信息，以便在发现不平衡时，算法可以立刻停止。这里我使用了异常机制，在出现不平衡后断言不成立，会抛出异常。

递归地计算左右子树的深度，发现不平衡后，抛出异常，由此立刻退出递归调用。文章来源地址https://www.toymoban.com/news/detail-832856.html

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        try{
            throw_if_unbalance(root);
            return true;
        }catch(...){
            return false;
        }
    }
private:
    int throw_if_unbalance(TreeNode* node) {
        if(node == nullptr){
            return 0;
        }

        int left_depth = throw_if_unbalance(node->left);
        int right_depth = throw_if_unbalance(node->right);

        if(abs(left_depth - right_depth) > 1){
            throw exception();
        }
        return 1 + max(left_depth, right_depth);
    }
};

到了这里，关于【leetcode热题】平衡二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！