剑指 Offer 55 - II 平衡二叉树

Tag: 剑指-Offer Posted on 2022-02-27 17:02:58 Edited on 2022-02-27 17:03:12 Views: 177

概述

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/