class TreeNode{
int data;
TreeNode left;
TreeNode right;
}
//题目1：输入二叉树的根节点，返回数的最大深度
public class Main {
public static void main(String[] args) throws Exception {
TreeNode t = new TreeNode();
t.data = 2;
t.left = new TreeNode();
t.left.data = 1;
t.left.left = new TreeNode();
t.left.right = new TreeNode();
t.left.left.data = 4;
t.left.right.data = 5;
t.right = new TreeNode();
t.right.data = 3;
System.out.println(checkDepth(t));
}
public static int checkDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = checkDepth(root.left)+1;
int right = checkDepth(root.right)+1;
return Math.max(left,right);
}
}
//题目2：输入二叉树根节点，判断是否是平衡二叉树
//解法1：从根节点开始遍历每个节点，但每个节点都要重新计算深度，复杂度较高
public class Main {
public static void main(String[] args) throws Exception {
TreeNode t = new TreeNode();
t.data = 2;
t.left = new TreeNode();
t.left.data = 1;
t.left.left = new TreeNode();
t.left.right = new TreeNode();
t.left.left.data = 4;
t.left.right.data = 5;
t.right = new TreeNode();
t.right.data = 3;
System.out.println(isBalance(t));
}
public static boolean isBalance(TreeNode root){
if(root == null){
return true;
}
int left = checkDepth(root.left);
int right = checkDepth(root.right);
int diff = Math.abs(left-right);
if(diff>1){
return false;
}
return isBalance(root.left) && isBalance(root.right); //从根节点开始遍历左右子树
}
public static int checkDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = checkDepth(root.left)+1;
int right = checkDepth(root.right)+1;
return Math.max(left,right);
}
}
//解法2：采用后序遍历的方式进行检查，遍历每个节点时就已经提前记录了其左右子树的深度
public class Main {
public static void main(String[] args) throws Exception {
TreeNode t = new TreeNode();
t.data = 2;
t.left = new TreeNode();
t.left.data = 1;
t.left.left = new TreeNode();
t.left.left.left = new TreeNode();
t.left.right = new TreeNode();
t.left.left.data = 4;
t.left.left.left.data = 4;
t.left.right.data = 5;
t.right = new TreeNode();
t.right.data = 3;
System.out.println(isBalance(t));
}
public static boolean isBalance(TreeNode root){
if(isBalanceHelper(root) == -1){
return false;
}else{
return true;
}
}
public static int isBalanceHelper(TreeNode root) {
if(root == null){
return 0;
}
int left = isBalanceHelper(root.left); //先递归查看左子树
if(left == -1){
return -1;
}
int right = isBalanceHelper(root.right); //再递归查看右子树
if(right == -1){
return -1;
}
int diff = Math.abs(left-right); //如果深度差大于1，则不平衡
if(diff>1){
return -1;
}
return Math.max(left,right)+1; //返回左右子树较深的结果
}
}
