170.二叉树：平衡二叉树（力扣）

代码解决

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr, right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    // 递归计算二叉树的高度，同时检查是否平衡
    int height(TreeNode* root) {
        // 基本条件：如果节点为空，高度为0
        if (root == nullptr) return 0;

        // 递归计算左子树的高度
        int leftdeep = height(root->left);
        // 如果左子树不平衡，返回-1
        if (leftdeep == -1) return -1;

        // 递归计算右子树的高度
        int rightdeep = height(root->right);
        // 如果右子树不平衡，返回-1
        if (rightdeep == -1) return -1;

        // 如果左右子树高度差大于1，表示当前树不平衡，返回-1
        if (abs(leftdeep - rightdeep) > 1) return -1;

        // 否则返回当前树的高度，即左右子树高度的最大值加1
        return 1 + max(leftdeep, rightdeep);
    }
    
    // 判断二叉树是否平衡
    bool isBalanced(TreeNode* root) {
        // 调用height方法，如果返回值为-1，表示树不平衡，返回false
        return height(root) == -1 ? false : true;
    }
};

• TreeNode 结构体定义：

  • val：节点的整数值。
  • left：指向左子节点的指针。
  • right：指向右子节点的指针。

• Solution 类：

  • 包含两个方法：height 和 isBalanced。

• height 方法：

  • 这是一个递归函数，用来计算二叉树的高度，并检查树是否平衡。
  • 基本条件：如果 root 为 nullptr，则返回高度 0。
  • 递归计算左子树和右子树的高度：
    • 如果左子树的高度为 -1，表示左子树不平衡，直接返回 -1。
    • 如果右子树的高度为 -1，表示右子树不平衡，直接返回 -1。
  • 如果左右子树的高度差超过 1，表示当前树不平衡，返回 -1。
  • 否则，返回当前树的高度，即左右子树高度的最大值加 1。

• isBalanced 方法：

  • 这个方法调用 height 方法，如果返回值为 -1，表示树不平衡，返回 false。否则，返回 true，表示树是平衡的。