题目
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false示例 3：
输入：root = []
输出：true提示：
- 树中的节点数在范围
[0, 5000]内 -104 <= Node.val <= 104
解答
- 递归但空间复杂度较高的解法
本题可以使用递归的方法来解决。对于每一个节点，我们需要先递归遍历它的左右子树，计算它们的高度差。如果左右子树的高度差超过了1，那么这棵树就不是平衡二叉树。如果左右子树都是平衡二叉树，那么我们可以判断当前节点是不是平衡二叉树：如果左右子树的高度差不超过1，那么当前节点就是平衡二叉树。最后递归返回整棵树的平衡情况。
在递归函数中，我们需要同时返回当前节点的高度和平衡情况，因此可以使用pair<int, bool>来表示。其中，pair的第一个元素表示高度，第二个元素表示当前节点是否是平衡二叉树。同时，我们需要处理一些边界情况，例如空节点的高度为0，空节点也是平衡二叉树。C++代码实现如下：
/**
* 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:
bool isBalanced(TreeNode* root) {
return checkBalance(root).second;
}
pair<int, bool> checkBalance(TreeNode* node) {
if (!node) {
// 空节点为平衡二叉树
return make_pair(0, true);
}
auto left = checkBalance(node->left);
auto right = checkBalance(node->right);
if (left.second && right.second && abs(left.first - right.first) <= 1) {
// 左右子树都是平衡二叉树，且高度差不超过1
return make_pair(max(left.first, right.first) + 1, true);
}
// 左右子树不平衡，或者当前节点不平衡
return make_pair(0, false);
}
};
pair是C++ STL中的一个模板类，用于存储两个不同类型的变量。它将两个变量打包成一个整体，方便传递和使用。
但是它的内存占用过高，因为对于每个节点，它都要单独存一个bool变量用于表示节点是否为二叉树的平衡结点。因此需要进行优化。
- 递归，但优化内存占用
在题目中，我们使用了pair<int, bool>来表示每个节点的高度和平衡情况，但是这种方法会浪费一定的空间，因为每个节点都需要存储一个bool类型的变量。实际上，我们只需要判断每个节点是否平衡，因此可以使用一个int类型的变量来表示平衡情况：-1表示不平衡，非0表示平衡并且代表节点的高度。这样就可以减少空间的使用。
同时，我们可以将返回值从pair<int, bool>改为int，表示当前节点的高度。如果当前节点不是平衡二叉树，那么直接返回-1，否则返回节点的高度。
C++代码如下：
/**
* 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:
bool isBalanced(TreeNode* root) {
return checkBalance(root) != -1;
}
int checkBalance(TreeNode* node) {
if (!node) {
// 空节点为平衡二叉树
return 0;
}
int left = checkBalance(node->left);
int right = checkBalance(node->right);
if (left != -1 && right != -1 && abs(left - right) <= 1) {
// 左右子树都是平衡二叉树，且高度差不超过1
return max(left, right) + 1;
}
// 左右子树不平衡，或者当前节点不平衡
return -1;
}
};