刘珊睿_Theory level
获赞
46
粉丝
6
关注
10
看过 TA
69
北京邮电大学
2021
Java
IP属地:未知
暂未填写个人简介
私信
关注
2020-06-04 09:56
北京邮电大学 Java
【刷题日记】平衡二叉树早上又在LeetCode上提交了一遍,惊奇的发现(大惊小怪)在牛客网通过了在LeetCode上过不了又仔细细看了一遍平衡二叉树的定义发现一个重点:“每个节点”而之前那种方法明显只能判断根结点是否为平衡二叉树啊你个菜鸡!!以下是在LeetCode上改进的算法:class Solution {private:    int depth(TreeNode* root) {        if (!root) return 0;        return 1+max(depth(root->left), depth(root->right));    }public:    bool isBalanced(TreeNode* root) {        if (!root) return true;        bool isBalancedNode = false;        //判断此节点为平衡        if(abs(depth(root->left) - depth(root->right)) <= 1){            isBalancedNode = true;        }        //再判断这个节点的左右子节点是否为平衡        return isBalancedNode && isBalanced(root->left) && isBalanced(root->right);    }};这才完事儿~之后还有错误,还请有幸看到的大佬指正,万分感谢。
投递牛客等公司10个岗位
0 点赞 评论 收藏
分享
2020-06-03 10:25
北京邮电大学 Java
【刷题日记】之平衡二叉树由于平衡二叉树这个概念比较陌生,所以一直留着这个题没做(原谅自己的菜鸡本质。。。)意外地一次就通过了,小小地纪念一下。先上代码为敬://任意节点左右子树的深度差不超过1class Solution {private:    //计算节点子树的深度    int depth(TreeNode* root){        if(!root) return 0;        return 1 + max(depth(root->left),depth(root->right));    }public:    bool IsBalanced_Solution(TreeNode* pRoot) {        if(!pRoot) return true;                return abs(depth(pRoot->right) - depth(pRoot->left)) <= 1;    }};其实刚看到这题马上就联想到了计算二叉树深度那道题,但是怀疑自己的思路不严谨,就百度了一下,结果。。。大佬的思路有点看不懂。https://www.cnblogs.com/wanglei5205/p/8918624.html算了,还是自己来吧。思路还挺清晰的:1.写一个函数可以计算每一个节点的深度(包括叶子结点);2.再写一个函数,判断传入的根结点是否是平衡树,就是判断左右子树的高度差是否小于等于1。完事儿了,撒花🎉
投递百度等公司10个岗位
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客企业服务