剑指offer之判断二叉树是不是平衡二叉树

1 问题

判断二叉树是不是平衡二叉树

平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

2 代码实现

  

   

    

     

    
    

     

      int getTreeHeigh(Node *haed)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if (head == NULLL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       return 0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int left = getTreeHeigh(head->left);
     
    
   

    

     

    
    

     
 int right = getTreeHeigh(head->right);
     
    
   

    

     

    
    

     

       retur left > right ? (left + 1) : (right + 1);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int isBalancedTree(Node *head)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (head == NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		return NULL;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int left, right;
     
    
   

    

     

    
    

     
	left = isBalancedTree(head->left);
     
    
   

    

     

    
    

     
	right = isBalancedTree(head->right);
     
    
   

    

     

    
    

     
	int result = left - right;
     
    
   

    

     

    
    

     
	if (result > 1 || result < -1)
     
    
   

    

     

    
    

     

      		return false;
     
    
   

    

     

    
    

     

      	return isBalancedTree(head->left) && isBalancedTree(head-right);
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/91906713