110. 平衡二叉树-JZTXT

110. 平衡二叉树
/**
 * 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:
    //递归问题:返回左右子树的高度差状态, 如果高度差<2则返回最大的那个(子树的深度, 算最深的那个); 如果高度差>=2则返回-1
    int recur(TreeNode* cur)
    {
        //递归终止: 越过子节点 递归回来一个信息: 目前的子节点的深度为0
        if(cur == nullptr) return 0;
        //左右子树高度left==-1
        int left = recur(cur->left);
        if(left == -1) return -1;       //只要有一个节点的左右子树高度差的绝对值>=2, 这个就是非平衡树, 这个返回-1就病毒一样传播
        int right = recur(cur->right);
        if(right == -1) return -1;
        //递归到最深的时候肯定要越过子节点, 如果目前没有发现是非平衡树, 则返回目前的深度+1 
        //返回的时候已经把左右节点都递归完了
        return abs(left - right)<2 ? max(left,right) + 1:-1;
    }

    bool isBalanced(TreeNode* root) {
        //递归关系 当root左右子树高度差<2 or 左右子树高度差>=2 返回 -1 此子树不是平衡树.
        //左右子树的高度怎么得到呢, 根据下一层递归返回的深度
        return recur(root)!=-1;
    }
};