Java solution, Recursive, DFS, 3ms


  • -1
    C
       class TreeNode2{
    	private TreeNode2 left;
    	private TreeNode2 right;
    	private int height;
    	private boolean isBalanced;
    	
        private TreeNode2(int value){
        	height = value;
        }
        
        private void setHeight(){
        	if(null == this.left && null == this.right) this.height = 1;
        	else if(null == this.right) this.height =  this.left.height + 1;
        	else if(null == this.left) this.height = this.right.height + 1;
        	else this.height = Math.max(this.left.height, this.right.height) + 1;
        	return;
        }
        
        public String toString(){
        	return this.height + "," + this.isBalanced;
        }
    }
    
    public boolean isBalanced(TreeNode root){
    	TreeNode2 croot = copyTree(root);
    	return null == croot ? true : croot.isBalanced;
    }
    
    private TreeNode2 copyTree(TreeNode root){
    	if(null == root) return null;
    	//copy root
    	TreeNode2 croot = new TreeNode2(1);
    	//copy left subtree.
    	croot.left = copyTree(root.left);
    	//check whether left tree is balanced, if left tree is unbanlanced ,then return directly.
    	if(null != croot.left && ! croot.left.isBalanced){
    		croot.isBalanced = false;
    		return croot;
    	}
    	//copy right subtree
    	croot.right = copyTree(root.right);
    	if(null != croot.right && ! croot.right.isBalanced){
    		croot.isBalanced = false;
    		return croot;
    	}
    	int leftHeight = null == croot.left ? 0 : croot.left.height;
    	int rightHeight = null == croot.right ? 0 : croot.right.height;
    	if(Math.abs(leftHeight - rightHeight) > 1){
    		croot.isBalanced = false;
    	}
    	else{
    		croot.isBalanced = true;
    	}
    	croot.setHeight();
    	return croot;
    }

  • 0
    C
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.