平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

思路

平衡二叉树中每个节点的平衡因子只有三种可能：-1，0，1。遍历二叉树，只要有一个节点的平衡因子不是-1,0,1则二叉树的不是平衡二叉树，否则就是。比较直观的思路就是计算每个节点的左右子树的高度，然后看是否平衡。但是这样，时间复杂度为O(n²)，节点被重复遍历了。可以一遍遍历一遍统计，可以用遍历时，统计节点的高度，如果是不平衡的节点，设置其高度为-1，否则就是正常高度值。

代码

class Solution {
public:
    int height(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }
        int left = height(root->left);
        int right = height(root->right);
        if(left == -1 || right == -1 || abs(left-right) > 1) {
            return -1;
        }
        return max(left,right) + 1;
    }
    bool isBalanced(TreeNode* root) {
        return height(root) >= 0;
    }
};