LeetCode110 平衡二叉树

链接: https://leetcode-cn.com/problems/balanced-binary-tree/

题意

判断一棵树是不是平衡二叉树，判断左右结点的高度差是否相差不到1，若不是则不为平衡二叉树

解法

一是我们需要先处理子树的深度再进行比较，二是如果我们在处理子树时发现其已经不平衡了，则可以返回一个-1，使得所有其长辈节点可以避免多余的判断（剪枝）
虽然代码简单，但还是包含了一些细节的，值得记录

代码

class Solution {
public:
    int helper(TreeNode* root) {
        // 边计算高度边进行平衡的判断
        // -1表示不平衡 剪枝
        if (root == nullptr) return 0;
        int l = helper(root -> left), r = helper(root -> right);
        if (l == -1 || r == -1 || abs(l - r) > 1) return -1;
        return 1 + max(l, r);
    }
    bool isBalanced(TreeNode* root) {
        return helper(root) != -1;

    }
};