55-II. 平衡二叉树
1. 描述
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
2. 例子
示例 1:
给定二叉树 [3,9,20,null,null,15,7]，
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
返回 false 。
3. 限制
- 1 <= 树的结点个数 <= 10000
4. 题解
n 是 i_root 中的节点个数
时间复杂度: O(n)
空间复杂度: O(n)
也可以令返回是否平衡的递归函数同时返回深度和是否平衡，可以省去哈希表，但是不影响复杂度。
class Solution
{
private:
unordered_map<TreeNode*, int> subTreeDepth;
bool isTreeBalanced(TreeNode *i_root)
{
if(!i_root->left && !i_root->right)
{
subTreeDepth[i_root] = 1;
return true;
}
auto isLeftSubTreeBalanced = true, isRightSubTreeBalanced = true;
if(i_root->left) isLeftSubTreeBalanced = isTreeBalanced(i_root->left);
if(i_root->right) isRightSubTreeBalanced = isTreeBalanced(i_root->right);
subTreeDepth[i_root] = 1 + max(subTreeDepth[i_root->left], subTreeDepth[i_root->right]);
return isLeftSubTreeBalanced && isRightSubTreeBalanced && abs(subTreeDepth[i_root->left] - subTreeDepth[i_root->right]) <= 1;
}
public:
// bool isBalanced(TreeNode* root)
bool isBalanced(TreeNode *i_root)
{
if(!i_root) return true;
subTreeDepth[nullptr] = 0;
return isTreeBalanced(i_root);
}
};