04.04. 检查树平衡性
主要递归函数,计算节点node的深度
int getDepth(TreeNode* node) {
if (node == nullptr) return 0;
return std::max(getDepth(node->left), getDepth(node->right)) + 1;
}
平衡树对于所有节点有同样的性质:
任意一个节点,其两棵子树的高度差不超过 1。
bool isBalanced(TreeNode* root) {
if (!root) return true;
auto ld = getDepth(root->left);
auto rd = getDepth(root->right);
return (std::abs(ld - rd) < 2)
&& isBalanced(root->left) && isBalanced(root->right);
}
所以要对每一个子节点递归判断isBalanced
如下图 节点1左右子树深度相同,但是1并不是平衡树
