平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 1 /**
 2  * 
 3  * @author gentleKay
 4  * 题目描述
 5  * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 6  * 平衡二叉树的性质：
 7  * 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
 8  */
 9 
10 public class Main38 {
11 
12     public static void main(String[] args) {
13         // TODO Auto-generated method stub
14         TreeNode root = new TreeNode(1);
15         root.left = new TreeNode(2);
16         root.left.left = new TreeNode(4);
17         root.left.right = new TreeNode(5);
18     
19 //        root.right = new TreeNode(3);
20 //        root.right.right = new TreeNode(6);
21 //        root.right.right.right = new TreeNode(7);
22 //        root.right.right.right.right = new TreeNode(8);
23         boolean flag = Main38.IsBalanced_Solution(root);
24         System.out.println(flag);
25     }
26     
27     public static class TreeNode {
28         int val = 0;
29         TreeNode left = null;
30         TreeNode right = null;
31 
32         public TreeNode(int val) {
33             this.val = val;
34         }
35     }
36     
37     public static boolean IsBalanced_Solution(TreeNode root) {
38         if (root == null) {
39             return true;
40         }
41         int left = Depth(root.left);
42         int right = Depth(root.right);
43         if (Math.abs(left-right) > 1) {
44             return false;
45         }
46         return true;
47     }
48     
49     public static int Depth(TreeNode root) {
50         if (root == null) {
51             return 0;
52         }
53         int a = Depth(root.left)+1;
54         int b = Depth(root.right)+1;
55         return a>b ? a:b;
56     }
57 
58 }