平衡二叉树,c++

平衡二叉树

http://www.nowcoder.com/questionTerminal/8b3b95850edb4115918ecebdf1b4d222

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {

        auto res = find_deep(pRoot);
        if (res == -1)
            return false;
        else
            return true;
    }

    int find_deep(TreeNode* pRoot){
        if (pRoot == nullptr)
            return 0;
        auto right = find_deep(pRoot->right);
        auto left = find_deep(pRoot->left);
        if (right == -1 || left == -1)
            return -1;
        if (abs(right - left) > 1)
            return -1 ;
        else
            return max(right, left) + 1;
    }
};

平衡二叉树的性质是:是一颗空树或者左右高度差不超过1,且其子树都是平衡二叉树,由性质联想递归方法。
看了一下大家的思路,还是有点相似的。
1、递归函数的作用是判断当前节点的深度同时判断其是否为平衡树,
(1)当左右深度差值超过1,return -1;否则return 树深度
(2)若一个节点的一个子树已经不平衡,则直接返回 -1
2、感觉这样的递归在判断一个子树返回 -1后,其他线路的节点还在继续判断,不能提前终止,没想到啥好方法。
欢迎交流指正!!!

全部评论
17行可以拆成两句分别放在15行和16行后面,相当于剪枝
点赞 回复 分享
发布于 2020-03-27 22:03

相关推荐

06-06 03:40
已编辑
电子科技大学 Java
在秋招的小白菜很想养修勾:一眼 苍穹外卖+谷粒商城,项目换一换吧,可以找一些付费知识星球博主带带,避免烂大街。多投投大厂,背背八股,你这学历乱杀了,等实习经验到位,到时候大厂闭眼选
投递美团等公司8个岗位
点赞 评论 收藏
分享
程序员牛肉:主要是因为小厂的资金本来就很吃紧,所以更喜欢有实习经历的同学。来了就能上手。 而大厂因为钱多,实习生一天三四百的就不算事。所以愿意培养你,在面试的时候也就不在乎你有没有实习(除非是同级别大厂的实习。) 按照你的简历来看,同质化太严重了。项目也很烂大街。 要么换项目,要么考研。 你现在选择工作的话,前景不是很好了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务