package leetcode.easy;

/**

 * Definition for a binary tree node. public class TreeNode { int val; TreeNode

 * left; TreeNode right; TreeNode(int x) { val = x; } }

 */

public class BalancedBinaryTree {

	public boolean isBalanced(TreeNode root) {

		if (null == root) {

			return true;

		} else {

			return (Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1) && isBalanced(root.left)

					&& isBalanced(root.right);

		}

	}

	private static int maxDepth(TreeNode root) {

		if (null == root) {

			return 0;

		} else {

			return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));

		}

	}

	@org.junit.Test

	public void test1() {

		TreeNode tn11 = new TreeNode(3);

		TreeNode tn21 = new TreeNode(9);

		TreeNode tn22 = new TreeNode(20);

		TreeNode tn33 = new TreeNode(15);

		TreeNode tn34 = new TreeNode(7);

		tn11.left = tn21;

		tn11.right = tn22;

		tn21.left = null;

		tn21.right = null;

		tn22.left = tn33;

		tn22.right = tn34;

		tn33.left = null;

		tn33.right = null;

		tn34.left = null;

		tn34.right = null;

		System.out.print(isBalanced(tn11));

	}

	@org.junit.Test

	public void test2() {

		TreeNode tn11 = new TreeNode(1);

		TreeNode tn21 = new TreeNode(2);

		TreeNode tn22 = new TreeNode(2);

		TreeNode tn31 = new TreeNode(3);

		TreeNode tn32 = new TreeNode(3);

		TreeNode tn41 = new TreeNode(4);

		TreeNode tn42 = new TreeNode(4);

		tn11.left = tn21;

		tn11.right = tn22;

		tn21.left = tn31;

		tn21.right = tn32;

		tn22.left = null;

		tn22.right = null;

		tn31.left = tn41;

		tn31.right = tn42;

		tn32.left = null;

		tn32.right = null;

		tn41.left = null;

		tn41.right = null;

		tn42.left = null;

		tn42.right = null;

		System.out.print(isBalanced(tn11));

	}

}