判断平衡二叉树

1.题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

2.具体算法

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot==NULL)
            return true;//当根节点为空是，返回true
        int LeftDepth = Get_Depth(pRoot->left);//定义LeftDepth为左子树的深度
        int RightDepth = Get_Depth(pRoot->right);//定义RightDepth为右子树的深度
        if(LeftDepth-RightDepth>1||RightDepth-LeftDepth>1)//判断左右子树的深度相差是否大于1
            return false;
        else{
            return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);//递归判断每个子树都否都为平衡二叉树
        }
    
    }
    int Get_Depth(TreeNode* pRoot){//定义Get_Depth(TreeNode* pRoot)函数计算子树的深度
        if(pRoot==NULL)
             return 0;
        int Left_Depth = Get_Depth(pRoot->left);
        int Right_Depth = Get_Depth(pRoot->right);
        return Left_Depth>Right_Depth?Left_Depth+1:Right_Depth+1;
    }
};

3.算法总结

• 要判断输入的二叉树是否为平衡二叉树，首先要理解什么是平衡二叉树，平衡二叉树（AVL）：它或者是一颗空树，或者具有以下性质的二叉树：它的左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
• 算法思路：
  1）先判断根节点是否为空，若为空，则判断为平衡二叉树；若不为空，则继续判断；
  2）当根节点不为空时，计算左子树和右子树的深度，判断左右子树的深度差的绝对值是否大于1 ，若大于1，则可判断该二叉树不为平衡二叉树；若深度差的绝对值小于等于1，则继续判断。
  3）当深度差的绝对值小于等于1时，则继续判断以此时根节点的左右孩子节点为根节点的子树是否为平衡二叉树，从根节点向叶子节点递归判断，若所有的子树都为平衡二叉树，则输入的二叉树为平衡二叉树；否则不为平衡二叉树。