/**

* Author: 王俊超

* Date: 2015-06-13

* Time: 16:39

* Declaration: All Rights Reserved !!!

*/

public class Test39 {

private static class BinaryTreeNode {

int val;

BinaryTreeNode left;

BinaryTreeNode right;

public BinaryTreeNode() {

}

public BinaryTreeNode(int val) {

this.val = val;

}

}

public static int treeDepth(BinaryTreeNode root) {

if (root == null) {

return 0;

}

int left = treeDepth(root.left);

int right = treeDepth(root.right);

return left > right ? (left + 1) : (right + 1);

}

/**

* 判断是否是平衡二叉树，第一种解法

*

* @param root

* @return

*/

public static boolean isBalanced(BinaryTreeNode root) {

if (root == null) {

return true;

}

int left = treeDepth(root.left);

int right = treeDepth(root.right);

int diff = left - right;

if (diff > 1 || diff < -1) {

return false;

}

return isBalanced(root.left) && isBalanced(root.right);

}

/**

* 判断是否是平衡二叉树，第二种解法

*

* @param root

* @return

*/

public static boolean isBalanced2(BinaryTreeNode root) {

int[] depth = new int[1];

return isBalancedHelper(root, depth);

}

public static boolean isBalancedHelper(BinaryTreeNode root, int[] depth) {

if (root == null) {

depth[0] = 0;

return true;

}

int[] left = new int[1];

int[] right = new int[1];

if (isBalancedHelper(root.left, left) && isBalancedHelper(root.right, right)) {

int diff = left[0] - right[0];

if (diff >= -1 && diff <= 1) {

depth[0] = 1 + (left[0] > right[0] ? left[0] : right[0]);

return true;

}

}

return false;

}

public static void main(String[] args) {

test1();

test2();

test3();

test4();

}

// 完全二叉树

// 1

// / \

// 2 3

// /\ / \

// 4 5 6 7

private static void test1() {

BinaryTreeNode n1 = new BinaryTreeNode(1);

BinaryTreeNode n2 = new BinaryTreeNode(1);

BinaryTreeNode n3 = new BinaryTreeNode(1);

BinaryTreeNode n4 = new BinaryTreeNode(1);

BinaryTreeNode n5 = new BinaryTreeNode(1);

BinaryTreeNode n6 = new BinaryTreeNode(1);

BinaryTreeNode n7 = new BinaryTreeNode(1);

n1.left = n2;

n1.right = n3;

n2.left = n4;

n2.right = n5;

n3.left = n6;

n3.right = n7;

System.out.println(isBalanced(n1));

System.out.println(isBalanced2(n1));

System.out.println("----------------");

}

// 不是完全二叉树，但是平衡二叉树

// 1

// / \

// 2 3

// /\ \

// 4 5 6

// /

// 7

private static void test2() {

BinaryTreeNode n1 = new BinaryTreeNode(1);

BinaryTreeNode n2 = new BinaryTreeNode(1);

BinaryTreeNode n3 = new BinaryTreeNode(1);

BinaryTreeNode n4 = new BinaryTreeNode(1);

BinaryTreeNode n5 = new BinaryTreeNode(1);

BinaryTreeNode n6 = new BinaryTreeNode(1);

BinaryTreeNode n7 = new BinaryTreeNode(1);

n1.left = n2;

n1.right = n3;

n2.left = n4;

n2.right = n5;

n5.left = n7;

n3.right = n6;

System.out.println(isBalanced(n1));

System.out.println(isBalanced2(n1));

System.out.println("----------------");

}

// 不是平衡二叉树

// 1

// / \

// 2 3

// /\

// 4 5

// /

// 7

private static void test3() {

BinaryTreeNode n1 = new BinaryTreeNode(1);

BinaryTreeNode n2 = new BinaryTreeNode(1);

BinaryTreeNode n3 = new BinaryTreeNode(1);

BinaryTreeNode n4 = new BinaryTreeNode(1);

BinaryTreeNode n5 = new BinaryTreeNode(1);

BinaryTreeNode n6 = new BinaryTreeNode(1);

BinaryTreeNode n7 = new BinaryTreeNode(1);

n1.left = n2;

n1.right = n3;

n2.left = n4;

n2.right = n5;

n5.left = n7;

System.out.println(isBalanced(n1));

System.out.println(isBalanced2(n1));

System.out.println("----------------");

}

// 1

// /

// 2

// /

// 3

// /

// 4

// /

// 5

private static void test4() {

BinaryTreeNode n1 = new BinaryTreeNode(1);

BinaryTreeNode n2 = new BinaryTreeNode(1);

BinaryTreeNode n3 = new BinaryTreeNode(1);

BinaryTreeNode n4 = new BinaryTreeNode(1);

BinaryTreeNode n5 = new BinaryTreeNode(1);

BinaryTreeNode n6 = new BinaryTreeNode(1);

BinaryTreeNode n7 = new BinaryTreeNode(1);

n1.left = n2;

n2.left = n3;

n3.left = n4;

n4.left = n5;

System.out.println(isBalanced(n1));

System.out.println(isBalanced2(n1));

System.out.println("----------------");

}

// 1

// \

// 2

// \

// 3

// \

// 4

// \

// 5

private static void test5() {

BinaryTreeNode n1 = new BinaryTreeNode(1);

BinaryTreeNode n2 = new BinaryTreeNode(1);

BinaryTreeNode n3 = new BinaryTreeNode(1);

BinaryTreeNode n4 = new BinaryTreeNode(1);

BinaryTreeNode n5 = new BinaryTreeNode(1);

BinaryTreeNode n6 = new BinaryTreeNode(1);

BinaryTreeNode n7 = new BinaryTreeNode(1);

n1.right = n2;

n2.right = n3;

n3.right = n4;

n4.right = n5;

System.out.println(isBalanced(n1));

System.out.println(isBalanced2(n1));

System.out.println("----------------");

}

}