leetcode 判断平衡二叉树

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

深度搜索,如果有一个子树|左深度-右深度|>1,直接设置balanced=false(初始化为true),设置之后不再进行判断,尽快退出递归,输出false

 

 

public class solution {
    //static boolean balanced = true;
    //最好不要用static ,
    //因为leetcode不停得在测试各种用例,balanced数值可能还是上次运行的结果
    //如果要用static,可以在调用isBalanced时,再设置一次balanced=true;
    public boolean balanced = true;
    public boolean isBalanced(TreeNode root) {
        int rightDepth = 0;
        int leftDepth = 0;
        
        if (root == null)
            return true;

        ChildNodeDepth(root);
        return balanced;
    }
    
    public int ChildNodeDepth(TreeNode root){
        int rightDepth = 0;
        int leftDepth = 0;
        
        if (root == null) return 0;
        if (!balanced) return 0;
                
        rightDepth = ChildNodeDepth(root.right) + 1;
        leftDepth = ChildNodeDepth(root.left) + 1;
        
        
        //balanced = Math.abs(rightDepth - leftDepth) > 1 ? false : true;
        //这种方法可能导致balanced先设置false,后又恢复true
        if (Math.abs(rightDepth - leftDepth) > 1)
            balanced = false;

        return rightDepth > leftDepth ? rightDepth : leftDepth;
    }
}

Tagged on: , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>