题解 | #判断是不是平衡二叉树#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pRoot TreeNode类
 * @return bool布尔型
 */
//解决方法：将val属性给当成二叉树的height属性
//执行以下步骤
//1.利用层序遍历得节点到每个节点（前序，中序，后续都可以）
//2.在遍历中将所有的节点的值（val）给初始化为0，利用递归来更新节点高度
//3.在遍历中更新节点的高度
//4.在遍历中计算每个复杂度节点的平衡因子，判断是不是二叉树
//()总共利用三次层序遍历
//(时间复杂度o(n),空间复杂度o(1))
typedef struct queue {
    struct TreeNode* data[500];
    int size;
} queue;
//初始化队列
queue* init_queue3() {
    queue* my_queue = (queue*)malloc(sizeof(queue));
    if (my_queue == NULL) {
        return NULL;
    }
    for (int i = 0; i < 500; i++) {
        my_queue->data[i] = NULL;
    }
    my_queue->size = 0;
    return my_queue;
}
//入队
void push_queue3(queue* my_queue, struct TreeNode* data) {
    if (my_queue == NULL) {
        return;
    }
    my_queue->data[my_queue->size] = data;
    my_queue->size++;
}
//出队并返回队头元素
struct TreeNode* pop_queue3(queue* my_queue) {
    if (my_queue == NULL || my_queue->size == 0) {
        return NULL;
    }
    struct TreeNode* value = my_queue->data[0];
    for (int i = 0; i < my_queue->size - 1; i++) {
        my_queue->data[i] = my_queue->data[i + 1];
    }
    my_queue->size--;
    return value;
}
//判断队列是否为空
bool isEmpty3(queue* my_queue) {
    if (my_queue == NULL || my_queue->size == 0) {
        return true;
    }
    return false;
}
//比较节点那个子树更高并返回
int compare2(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}
//递归更新高度
int updata_high(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    node->val = 1 + compare2(updata_high(node->left), updata_high(node->right));
    return node->val;
}
//计算平衡因子
int calculate_balance(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    if (node->left == NULL && node->right != NULL) {
        return node->right->val;
    }
    if (node->left != NULL && node->right == NULL) {
        return node->left->val;
    }
    if (node->left != NULL && node->right != NULL) {
        return node->left->val > node->right->val ? node->left->val - node->right->val :
               node->right->val - node->left->val;
    }
    return 0;
}
//层序遍历初始化val
void init_val(struct TreeNode* node) {
    if (node == NULL) {
        return;
    }
    queue* my_queue = init_queue3();
    struct TreeNode* node1 = node;
    push_queue3(my_queue, node);
    while (!isEmpty3(my_queue)) {
        node1 = pop_queue3(my_queue);
        node1->val = 0;
        if (node1->left != NULL) {
            push_queue3(my_queue, node1->left);
        }
        if (node1->right != NULL) {
            push_queue3(my_queue, node1->right);
        }
    }
}
//层序遍历更新高度
void val_to_high(struct TreeNode* node) {
    if (node == NULL) {
        return;
    }
    queue* my_queue = init_queue3();
    struct TreeNode* node1 = node;
    push_queue3(my_queue, node);
    while (!isEmpty3(my_queue)) {
        node1 = pop_queue3(my_queue);
        updata_high(node1);
        if (node1->left != NULL) {
            push_queue3(my_queue, node1->left);
        }
        if (node1->right != NULL) {
            push_queue3(my_queue, node1->right);
        }
    }
}
//计算平衡因子的同时判断是否为平衡二叉树
bool IsBalanced_Solution(struct TreeNode* pRoot) {
    // write code here
    if (pRoot == NULL) {
        return true;
    }
    init_val(pRoot);
    val_to_high(pRoot);
    queue* my_queue = init_queue3();
    struct TreeNode* node = pRoot;
    push_queue3(my_queue, pRoot);
    while (!isEmpty3(my_queue)) {
        node = pop_queue3(my_queue);
        int balance = calculate_balance(node);//平衡因子计算
        if (balance < -1 || balance > 1) {
            return false;
        }
        if (node->left != NULL) {
            push_queue3(my_queue, node->left);
        }
        if (node->right != NULL) {

            push_queue3(my_queue, node->right);
        }
    }
    return true;
}