leetcode110-平衡二叉树

110. 平衡二叉树

这道题很容易联想到 104. 二叉树的最大深度 的做法。一开始做的时候就知道可以用递归，但是又想到了左右子树的高度相差不大于1，但是子树的子树相差大于1的情况，就开始往这方面多想了。

看了别人的题解才知道，左右子树相差大于1确实可以直接判断为false。

至于子树的子树的情况就要递归调用函数自身了，判断左子树是否为平衡树和判断右子树是否为平衡树再取并，就考虑了子树的子树相差大于1的情况。

这种自顶向下的方法时间复杂度挺大的，效率更高的还得是自底向上的递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root)
    {
        if(root==nullptr) return 0;
        int leftCount = maxDepth(root->left);
        int rightCount = maxDepth(root->right);
        return max(leftCount,rightCount)+1;
    }
    bool isBalanced(TreeNode* root) {
        if(root==nullptr) return true;
        if(abs(maxDepth(root->left)-maxDepth(root->right)) > 1) return false;
        return isBalanced(root->left)&&isBalanced(root->right);
    }
};

自底向上，不太好理解。-1是非平衡的一个标记，若返回的不是-1，则返回树的最大深度。一旦某一个子树不是平衡树，则一直回到上一层返回-1

class Solution {
public:
    int recur(TreeNode* root)
    {
        if(root==nullptr) return 0;
        int _left = recur(root->left);
        if(_left==-1) return -1;
        int _right = recur(root->right);
        if(_right==-1) return -1;
        return abs(_left - _right) < 2 ? max(_left,_right) + 1 : -1;
    }
    bool isBalanced(TreeNode* root)
    {
        return recur(root)!=-1;
    }
};