你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

【每日一题043】leetcode-110

2021-11-26 7:33:54

目录

  • 题目
  • 思路
  • 相关思考
  • 代码(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;
    }
};