110. 平衡二叉树

题目：
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

解法思路：
1）通过遍历每一个节点，然后返回节点对应的左右子树的高度来判断该节点是否是左右平衡的，采取从根节点开始的思路可以实现，但是该方法对于子树的高度计算存在重复计算（参考前序遍历）
代码实现如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 自顶向下的遍历方法  计算存在冗余
int max(int a, int b)
{
    if (a > b) {
        return a;
    }
    return b;
}

int hight(struct TreeNode* root)
{
    if (root == NULL) {
        return 0;
    }
    
    return 1 + max(hight(root -> left), hight(root -> right));
}

int ab(int a, int b)
{
    if (a > b) {
        return a - b;
    }
    return b - a;
}
bool isBalanced(struct TreeNode* root)
{

    if (root == NULL) {
        return true;
    }
    
    int leftH;
    int rightH;
    leftH = hight(root -> left);
    rightH = hight(root -> right);

    return (ab(leftH, rightH) < 2) &&
            isBalanced(root -> left) &&
            isBalanced(root -> right);

}

2）参考二叉树的后序遍历，从叶子节点开始判断，通过递归，在判断左右子树是平衡的以后，再判断对应的根节点是否为平衡的，从而实现对整个树的判断

代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//自底向上的遍历方法
int max(int a, int b)
{
    if (a > b) {
        return a;
    }
    return b;
}

int ab(int a, int b)
{
    if (a > b) {
        return a - b;
    }
    return b - a;
}

bool isBalancedHelper(struct TreeNode*root, int* hight)
{
    if (root == NULL) {
        *hight = 0;
        return true;
    }

    int leftH = 0;
    int rightH = 0;

    if (isBalancedHelper(root -> left, &leftH) &&
        isBalancedHelper(root -> right, &rightH) &&
        (ab(leftH, rightH) < 2)) {

        *hight = max(leftH, rightH) + 1;
        return true;
    }
    return false;
}
bool isBalanced(struct TreeNode* root)
{
    int hight;
    return isBalancedHelper(root, &hight);
}

本文地址：https://blog.csdn.net/weixin_38853761/article/details/107646787