后序遍历,当不满足返回-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;

    }
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务