后序遍历,当不满足返回-1

平衡二叉树

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

减少重复访问,后续遍历,当Math.abs(left-right)>1,则直接返回-1.最后平衡判断 recur(root)!=-1。

    /**
     * 输入一棵二叉树,判断该二叉树是否是平衡二叉树。
     * @param root 二叉树
     * @return 判断该二叉树是否是平衡二叉树。
     */
    public boolean IsBalanced_Solution(TreeNode root) {
        return BalancedRecur(root)!=-1;


    }
    public  int BalancedRecur(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=BalancedRecur(root.left);
        if(left==-1) return -1;
        int right=BalancedRecur(root.right);
        if(right==-1){
            return -1;
        }
        return Math.abs(left-right)<=1?Math.max(left,right)+1:-1;

    }
全部评论

相关推荐

uu们,拒offer时hr很生气怎么办我哭死
爱睡觉的冰箱哥:人家回收你的offer,或者oc后没给你发offer的时候可不会愧疚你,所以你拒了也没必要愧疚他。
点赞 评论 收藏
分享
半解316:内容充实,细节需要修改一下。 1,整体压缩为一页。所有内容顶格。 2,项目描述删除,直接写个人工作量 修改完之后还需要建议,可以私聊
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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