4_1.java

CC150 4.1

/*
4.1
Implement a function to check if a binary tree is balanced. 
For the purposes of this question, a balanced tree is defined to be a tree such that the heights 
of the two subtrees of any node never differ by more than one.
*/


// 时间复杂度: O(n), n为节点个数
// 空间复杂度: O(h), h为树高度。

package cc150Test;


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

public class Test {
	
	public static boolean isBalanced(TreeNode root){
		if( root == null ){
			return true;
		}
		if( getHeight(root) == -1 ){
			return false;
		}
		return true;
	}

	public static int getHeight(TreeNode root){
		if( root == null ){
			return 0;
		}
		int leftHeight = getHeight(root.left);
		int rightHeight = getHeight(root.right);
		if( leftHeight == -1 || rightHeight == -1 || Math.abs( leftHeight - rightHeight ) > 1 ){
			return -1;
		}
		return Math.max(leftHeight,rightHeight) + 1;
	}
	
	public static TreeNode test1(){
		TreeNode node1 = new TreeNode(7);
		TreeNode node2 = new TreeNode(4);
		TreeNode node3 = new TreeNode(9);
		node1.left = node2; node1.right = node3;
		TreeNode node4 = new TreeNode(2);
		TreeNode node5 = new TreeNode(5);
		node2.left = node4; node2.right = node5;
		TreeNode node6 = new TreeNode(8);
		TreeNode node7 = new TreeNode(10);
		node3.left = node6; node3.right = node7;
		TreeNode node8 = new TreeNode(8);
		TreeNode node9 = new TreeNode(10);
		node4.left = node8; node4.right = node9;
		TreeNode node10 = new TreeNode(10);
		node5.right = node10;
		TreeNode node11 = new TreeNode(11);
		node7.right = node11;
		TreeNode node12 = new TreeNode(0);
		node8.left = node12;
		return node1;
	}
	public static TreeNode test2(){
		TreeNode node1 = new TreeNode(7);
		TreeNode node2 = new TreeNode(4);
		TreeNode node3 = new TreeNode(9);
		node1.left = node2; node1.right = node3;
		TreeNode node4 = new TreeNode(2);
		TreeNode node5 = new TreeNode(5);
		node2.left = node4; node2.right = node5;
		//TreeNode node6 = new TreeNode(8);
		TreeNode node7 = new TreeNode(10);
		//node3.left = node6; 
		node3.right = node7;
		TreeNode node8 = new TreeNode(8);
		TreeNode node9 = new TreeNode(10);
		node4.left = node8; node4.right = node9;
		TreeNode node10 = new TreeNode(10);
		node5.right = node10;
		TreeNode node11 = new TreeNode(11);
		node7.right = node11;
		TreeNode node12 = new TreeNode(0);
		node8.left = node12;
		return node1;
	}

	public static TreeNode test3(){
		TreeNode node1 = new TreeNode(7);
		TreeNode node2 = new TreeNode(4);
		node1.left = node2;
		return node1;
	}

	public static TreeNode test4(){
		TreeNode node1 = new TreeNode(7);
		TreeNode node2 = new TreeNode(4);
		TreeNode node3 = new TreeNode(9);
		node1.right = node2;
		node2.right = node3;
		return node1;
	}

	public static TreeNode test5(){
		TreeNode node1 = new TreeNode(7);
		TreeNode node2 = new TreeNode(4);
		TreeNode node3 = new TreeNode(9);
		node1.left = node2;
		node1.right = node3;
		return node1;
	}

	public static TreeNode test6(){
		TreeNode node1 = null;
		return node1;
	}

	public static void main(String[] args) {	
		

		TreeNode root1 = test1();
		System.out.println(isBalanced(root1));

		TreeNode root2 = test2();
		System.out.println(isBalanced(root2));

		TreeNode root3 = test3();
		System.out.println(isBalanced(root3));

		TreeNode root4 = test4();
		System.out.println(isBalanced(root4));

		TreeNode root5 = test5();
		System.out.println(isBalanced(root5));

		TreeNode root6 = test6();
		System.out.println(isBalanced(root6));		
	
	}		
}