110. 平衡二叉树

Problem: 110. 平衡二叉树

思路

这题也是自己的想法捏(￣▽￣)*；

取得左右子树的最大值，相减，大于1就不是平衡二叉树了。

剪枝 if (res == false) return 0;

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    bool res = true;
    int backForeach(TreeNode* node,bool flag){
        if (res == false) return 0;
        if(node == nullptr) {
            return 0;
        }
        int left = backForeach(node->left,true) + 1;
        int right = backForeach(node->right,false) + 1;
        if(std::abs(left - right) > 1) {
            res = false;
        }
        return std::max(left,right); 
    }
    bool isBalanced(TreeNode* root) {
        backForeach(root,true);
        return res;
    }
};