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) {// 基本条件：如果节点为空，高度为0if (root == nullptr) return 0;// 递归计算左子树的高度int leftdeep = height(root->left);// 如果左子树不平衡，返回-1if (leftdeep == -1) return -1;// 递归计算右子树的高度int rightdeep = height(root->right);// 如果右子树不平衡，返回-1if (rightdeep == -1) return -1;// 如果左右子树高度差大于1，表示当前树不平衡，返回-1if (abs(leftdeep - rightdeep) > 1) return -1;// 否则返回当前树的高度，即左右子树高度的最大值加1return 1 + max(leftdeep, rightdeep);}// 判断二叉树是否平衡bool isBalanced(TreeNode* root) {// 调用height方法，如果返回值为-1，表示树不平衡，返回falsereturn 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，表示树是平衡的。