LeetCode110. 平衡二叉树
平衡二叉树定义：|左子树高度-右子树高度| <= 1踩坑点：
不能通过根节点的左右子树高度来直接判断是否为平衡二叉树，e.g:假如根节点左子树为左斜树，右子树为右斜树，且两棵子树个数相同，此时根节点左右子树高度相同，但不是平衡二叉树。
因此还是需要一层层地往下判断
class Solution {
public:
int max(int a, int b)
{
return a > b ? a : b;
}
int getHeight(TreeNode* root)
{
if (root == nullptr) return 0;
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return max(leftHeight, rightHeight) + 1;
}
bool isBalanced(TreeNode* root)
{
bool res;
if (root == nullptr) return true;
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
if (abs((leftHeight - rightHeight)) <= 1)
{
if(!isBalanced(root->left)) return false;
if(!isBalanced(root->right)) return false;
return true;
}
else
return false;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]