LeetCode 题解

积跬步，至千里。

检查平衡性

分类：程序员面试金典题解 标签： 树 深度优先搜索 发布于：2020-05-20 ID：4.04

题目描述

来源于 https://leetcode-cn.com/

实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。


示例 1:<pre>给定二叉树 [3,9,20,null,null,15,7]
3
/ &#92
9 20
/ &#92
15 7
返回 true 。</pre>示例 2:
<pre>给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ &#92
2 2
/ &#92
3 3
/ &#92
4 4
返回 false 。</pre>

解法：

递归地计算左右子树的深度，发现不平衡后，抛出异常，由此立刻退出递归调用。

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);
    }
};