判断一棵树是否是平衡二叉树

struct TreeNode{  
    TreeNode *leftChild;  
    TreeNode *rightChild;  
    int data;  
};  
  
int getHeight(const TreeNode* root){  
    if( root == nullptr){  
        return 0;  
    }  
      
    return max(getHeight(root->leftChild), getHeight(root->rightChild)) + 1;  //返回一个节点左右子树的最大高度。
}  
  
bool isBalanced(const TreeNode* root){  
    if( root == nullptr){  
        return true;  //根为控返回true即平衡
    }  
      
    int heightDiff = abs(getHeight(root->leftChild) - getHeight(root->rightChild));  //判断左右最大子树是否为平衡
    if( heightDiff > 1){  
        return false;  
    }  
    else{  
        return isBalanced(root->leftChild) && isBalanced(root->rightChild);  //如果平衡，判断左子树是否为平衡，右子树是否为平衡。递归到最后一层，若无false为则为平衡二叉树。
    }  
}
    --------------------- 

改进后的代码，省去每次递归都需要计算子树长度。

int checkHeight(const TreeNode* root){  
    if( root == nullptr){  
        return 0;  
    }  
    // check the left subtree is balanced or not.  
    int leftHeight = checkHeight(root->leftChild);  //接收 最大高度，或者非平衡树返回值。
    if( leftHeight == -1 ){  
        return -1;  
    }  
      
    // check the right subtree is balanced or not.  
    int rightHeight = checkHeight(root->rightChild);  
    if( rightHeight == -1){  
        return -1;  
    }  
      
    // check the current tree is balanced or not.  
    int diff = leftHeight - rightHeight;  //判断左右子树高度差，若不平衡返回-1。
    if( abs(diff) > 1){  
        return -1;  
    }  
    else{  
        // return the tree height.  
        return max(leftHeight, rightHeight) + 1;  //否则返回子树的最大高度给节点。
    }  
}  
bool isBalanced(const TreeNode* root){  
    return ( checkHeight(root) == -1 )? false:true;  //判断树是否平衡。
} 

转载于：https://www.cnblogs.com/anzhsoft/p/3602982.html
作者：anzhsoft