目录
- 题目
- 思路
- 相关思考
- 代码(C++/原创)
题目
题目来源
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
思路
本质上可以转化为求树高进行比较的问题,通过对左右子树高度的比较来得出最后的结论
相关思考
提交后发现这种方法内存消耗较大,不知是否有改进的方法
代码(C++/原创)
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root==nullptr) return true;
if(root->left==NULL&&root->right==NULL) return true;
if(abs(treeHight(root->left)-treeHight(root->right))>1) return false;
else return isBalanced(root->left)&&isBalanced(root->right);
}
int treeHight(TreeNode* root)
{
if(root==nullptr) return 0;
else return max(treeHight(root->left),treeHight(root->right))+1;
}
};