平衡二叉树

编程练习

题目：输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路：平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。由定义可知可以用递归思想，并且上一道题中判断二叉树的深度的方法也可以拿过来用。

java代码如下：

public class IsBalanced_Tree {
	int leftdp=0;
	int rightdp=0;
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null) {
        	return true;
        }
    	boolean flag=false;
    	boolean left=IsBalanced_Solution(root.left);
    	boolean right=IsBalanced_Solution(root.left);
    	if(left) {
    		leftdp=TreeDepth(root.left);
    	}
    	if(right) {
    		rightdp=TreeDepth(root.right);
    	}
    	
    	if(leftdp-rightdp==1 || leftdp-rightdp==-1 || leftdp==rightdp) {
    		flag=true;
    	}
    	return flag;
    	
    }
    public int TreeDepth(TreeNode root) {
    	
    	if(root==null) {
    		return 0;
    	}
    	int left=TreeDepth(root.left);
    	int right=TreeDepth(root.right);
    	int max=0;
    	if(left>right) {
    		max=left;
    	}else {
    		max=right;
    	}
    	return max+1;
    }
    public static void main(String[] args) {
    	TreeNode root=new TreeNode(0);
		TreeNode node1=new TreeNode(1);
		TreeNode node2=new TreeNode(2);
		TreeNode node3=new TreeNode(3);
		TreeNode node4=new TreeNode(4);
		TreeNode node5=new TreeNode(5);
		TreeNode node6=new TreeNode(6);
		
		root.left=node1;
		root.right=null;
		node1.left=node3;
		node1.right=node4;
		node2.left=node5;
		node2.right=node6;
		
		IsBalanced_Tree bt=new IsBalanced_Tree();
		System.out.println(bt.IsBalanced_Solution(root));
	}
}