C语言平衡二叉树真题练习

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 计算当前任意一个节点(树)的高度（子函数）
int TreeDepth(struct TreeNode* root)
{
    // 当前节点为空
    if(root == NULL)
    {
        return 0;
    }
    // 当前节点不为空，分别计算它的左右子树的高度
    int leftDepth = TreeDepth(root->left);
    int rightDepth = TreeDepth(root->right);
    // 当前节点(树)的高度
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
bool isBalanced(struct TreeNode* root){
    // 依次递归遍历完root的所有子树，分别判断当前子树是否为高度平衡二叉树
    // 当前树的根节点为空，说明其满足高度平衡的二叉树，返回true
    if(root == NULL)
    {
        return true;
    }
    // 当前树的根节点不为空，分别计算它左右子树的高度
    int leftDepth = TreeDepth(root->left);
    int rightDepth = TreeDepth(root->right);
    // 计算左右子树的高度差
    int ret = leftDepth > rightDepth ? leftDepth - rightDepth : rightDepth - leftDepth;
    // 高度差不超过1，才能继续往下递归遍历当前树的左右子树
    return ret <= 1 && isBalanced(root->left) && isBalanced(root->right);
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 计算当前树的高度，并判断当前树是否是平衡二叉树
int _isBalanced(struct TreeNode* root)
{
    // 先分别判断当前树的左/右子树是否平衡
    // 如果当前树的左/右子树中只要有一个不平衡，则全树就不平衡，返回-1（表示不平衡）
    // 如果当前树的左右子树都平衡，则继续判断当前树是否平衡
    // 1. 到叶子节点了，当前树根节点为空，说明是平衡的，则返回高度0
    if(root == NULL)
    {
        return 0;
    }
    // 2. 当前树根节点不为空
    // 计算左右子树的高度
    int leftTreeDepth = _isBalanced(root->left);
    int rightTreeDepth = _isBalanced(root->right);
    // 不平衡的3种情况：左子树高度为-1，右子树高度为-1，左右子树高度差>1
    if(leftTreeDepth == -1 || rightTreeDepth == -1 || abs(leftTreeDepth - rightTreeDepth) > 1)
    {
        return -1;
    }
    // 如果不满足上面3种情况，说明当前树是平衡的，返回当前树的高度
    return leftTreeDepth > rightTreeDepth ? leftTreeDepth + 1 : rightTreeDepth + 1;
}
bool isBalanced(struct TreeNode* root){
    // 递归遍历过程中：
    // 只要有一个子树高度为-1，说明整个树是不平衡的，返回false
    // 所有子树高度都不等于-1，说明整个树是平衡的，返回true
    return _isBalanced(root) != -1;
}