【数据结构】（平衡二叉树）判断二叉树是否是平衡二叉树

短命女 2021-10-29 14:50 400阅读 0赞

> **算法思想**：判断一棵树是否为平衡二叉树可以采取高度差的递归方式来判断这个方法比较简单但是复杂度较高（因为高度被重复计算了很多次）O（nlogn）

//递归求高度
    int height(BSTree *root){
        
    
    	if(!root)
    		return 0;
    	int left=height(root->lchild);
    	int right=height(root->rchild);
    	return left>right ? left+1:right+1;
    
    }
    //判断二叉树是否是平衡二叉树
    
    bool balanceJudge(BSTree *root){
        
    
    	if(!root)  //空树是平衡二叉树
    		return true; 
    	if(root->lchild&&root->rchild) //只含有一个结点也是平衡二叉树
    		return true;
    
    	int left=height(root->lchild); //计算左子树高度
    	int right=height(root->rchild); //计算右子树高度
    
    	int diff=left-right;
    	if(diff>1||diff<-1)  //判断以该根节点的树是否为平衡而叉树
    		return false;
    
    	return balanceJudge(root->lchild)&&balanceJudge(root->rchild); //当左子树和右子树都是平衡二叉树的时候返回ture；
    }

> **接下来就是尝试可不可以使用O(n)的算法来解决这个问题，能否通过一次计算高度的代码就判断出该树是否为平衡二叉树呢？答案是肯定的 我们对求高度的代码进行一次修改**  
> 核心就是在求解高度的基础上进行了平衡的判断本质上也就是求解高度

int  flag=1;
        int  height2(struct TreeNode *&root )
    		if(root==NULL)
    			return 0;
    		int left=height2(root->left);
    		int right=height2(root->right);
    		int diff=left-right;
    		if(diff>1||diff<-1)
    			flag= 0;
    		return left>right ? left+1:right+1;
    }
    bool isBalanced(struct TreeNode* root){
        
        height2(root);
        if(flag==1)
            return true; 
        else
            return false;
        
    }