题目

输入一棵二叉树，判断该二叉树是否是平衡二叉树

分析思路

1. 将每一个树的节点的深度计算出来，并存放到一定的数据结构中（下面是用的map结构），再进行每一个节点平衡二叉树的特点判断，只要有一个不满足就不是，否则就是；
2. 直接用递归的方法计算每一个节点它的左右子树是否平衡，有一个不平衡就放回-1，后面的节点就都不用计算了

代码

思路一的代码

class Solution {
public:
    map<TreeNode*,int> depthArr;
    int depth(TreeNode *node){
//         如果没有节点，直接返回0
        if(!node)
            return 0;
//         下面的代码就是为了计算出每一个节点的深度，并把它存在c++映射结构map中
        if(depthArr.find(node)!=depthArr.end())
            return depthArr[node];
        
        int leftDepth = depth(node->left);
        int rightDepth = depth(node->right);
//         至于加一就是加上自己本身
        return depthArr[node] = max(leftDepth,rightDepth)+1;
    }
    bool judge(TreeNode* root){
        if(!root)
            return true;
//             必须满足平衡二叉树的条件
            return abs(depthArr[root->left] - depthArr[root->right]) <= 1 &&judge(root->left) && judge(root->right);
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        depth(pRoot);
        return judge(pRoot);
    }
};

思路二的代码

class Solution {
public:
    map<TreeNode*,int> depthArr;
    int depth(TreeNode *node){
        if(!node) return 0;
        int leftdepth = depth(node->left);
        int rightdepth  = depth(node->right);
        
//         如果此节点的左右子树不平衡，就返回
        if(abs(leftdepth-rightdepth)>1){
            return -1;
        }
//         如果递归出来的左右子树函数结果是-1后就不用算后面的节点深度了
        if(leftdepth == -1)
            return -1;
        if(rightdepth == -1)
            return -1;
//         以上条件都不满足，则返回此节点的深度
            return max(leftdepth,rightdepth)+ 1;
            
        
    }

    bool IsBalanced_Solution(TreeNode* pRoot) {
        return depth(pRoot) != -1;
       
    }
};