剑指 Offer 55 - II 平衡二叉树

概述

https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

https://leetcode.com/problems/balanced-binary-tree/

递归法

递归计算左右子树的深度，如果发现不平衡就开始摆烂返回 INT_MAX，反正坏了一个就全坏了，破罐破摔呗。

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return helper(root) != INT_MAX;
    }
    
    int helper(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        int ld = helper(root->left);
        int rd = helper(root->right);
        if (ld == INT_MAX || rd == INT_MAX) return INT_MAX;
        if (abs(ld - rd) > 1) return INT_MAX;
        return 1 + max(ld, rd);
    }
};