LeetCode: Balanced Binary Tree

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.

Solution:

Recursion. Check if balanced for each node.

	public boolean isBalanced(TreeNode root) {
	if(root == null) return true;
	if(getDepth(root) == -1)
	return false;
	return true;
	}
	public int getDepth(TreeNode root){
	if(root == null) return 0;
	int l=getDepth(root.left);
	if(l==-1) return -1;
	int r=getDepth(root.right);
	if(r==-1) return -1;
	if(l-r>1 || l-r<-1) return -1;
	return 1+ Math.max(l, r);
	}

view raw gistfile1.java hosted with ❤ by GitHub

The following solution used reference in C++ (needs to be tested)

	bool isBalanced(TreeNode *root) {
	if(!root) return true;
	int depth = 0;
	return isBalancedRe(root, depth);
	}
	bool isBalancedRe(TreeNode *root, int &depth){
	if(!root){
	depth = 0;
	return true;
	}
	int hLeft,hRight;
	if(isBalancedRe(root->left, hLeft)&&isBalancedRe(root->right, hRight)){
	depth=1 + (hLeft>=hRight)? hLeft:hRight;
	if(abs(hLeft-hRight)>1) return false;
	else return true;
	}
	else return false;
	}

view raw gistfile1.cpp hosted with ❤ by GitHub