private class Node<E>{
        E data;
        Node<E> lchild;
        Node<E> rchild;

        Node(E element){
            this.data = element;
        }
    }

    /**
     * 左旋
     *
     * @param e
     * @return 返回的是左旋后的根节点，左旋后的根节点是原来根节点的右孩子，左旋后的根节点的左孩子需要嫁接到原来根节点的右孩子上，原来的根节点嫁接到左旋后根节点的左孩子上。temp对应上图中值为8的节点，root对应上图中值为4的节点。
     */
    private Node<E> leftRotate(Node<E> e){
        Node<E> temp = e.rchild;
        e.rchild = temp.lchild;
        temp.lchild = e;
        return temp;
    }

    /**
     * 右旋 返回的是右旋后的根节点，右旋后的根节点是原来根节点的左孩子，右旋后的根节点的右孩子需要嫁接到原来根节点的左孩子上，原来的根节点嫁接到右旋后根节点的右孩子上。temp对应上图中值为5的节点，root对应上图中值为9的节点。
     * @param e
     * @return
     */
    private Node<E> rightRotate(Node<E> e){
        Node<E> temp = e.lchild;
        e.lchild = temp.rchild;
        temp.rchild = e;
        return temp;
    }

/**
     * 先左旋再右旋
     * @param element
     * @return 返回的是LR旋转后的根节点，先对根节点的左子树左旋，再整体右旋。root对应上图中值为9的节点。
     */
    private Node<E> leftRightRotate(Node<E> element){

        //先对element的左子树左旋
        element.lchild = this.leftRotate(element.lchild);
        //再对element右旋
        return rightRotate(element);
    }

/**
     *
     * @param element
     * @return 返回的是RL旋转后的根节点，先对根节点的右子树右旋，再整体左旋。root对应上图中值为4的节点。
     */
    private Node<E> rightLeftRotate(Node<E> element){

        //先对element的左子树左旋
        element.rchild = this.rightRotate(element.rchild);
        //再对element右旋
        return leftRotate(element);
    }

   public void add(E element) {
        Node<E> newNode = new Node<>(element);
        root = this.insert(root, newNode);
    }

    private Node<E> insert(Node<E> origin, Node<E> newNode) {
        if (origin == null) {

            origin = newNode;

        } else if (origin.data.compareTo(newNode.data) < 0) {
            //小
            origin.rchild = insert(origin.rchild, newNode);

        } else {
            //大等于
            origin.lchild = insert(origin.lchild, newNode);
        }

        boolean balance = isBalance(origin);
        if (!balance){
            origin = adjustment(origin, newNode);
        }

        return origin;
    }

    private Node<E> adjustment(Node<E> origin, Node<E> newNode) {

        if (origin.lchild != null && origin.lchild.data.compareTo(newNode.data) > 0 ){
            //新节点小于不平衡节点的左节点则是插入了左子树的左子树
            //RR型
            return rightRotate(origin);
        }

        if (origin.rchild.data.compareTo(newNode.data) < 0){
           //新节点大于不平衡节点的右节点则是插入了右子树的右子树
            //LL型
            return leftRotate(origin);
        }

        if (origin.lchild.data.compareTo(newNode.data) < 0 ){
            //新节点大于不平衡节点的左节点则是插入了左子树的右子树
            //LR型
            return leftRightRotate(origin);
        }

        if (origin.rchild.data.compareTo(newNode.data) > 0){
            //新节点小于不平衡节点的右节点则是插入了右子树的左子树
            //RL型
            return rightRotate(origin);
        }

        return origin;
    }

    private boolean isBalance(Node<E> origin) {
        return isBalancedTreeHelper(origin).balanced;
    }

    private TreeInfo isBalancedTreeHelper(Node<E> origin) {

        if (origin == null){
            return  new TreeInfo(-1, true);
        }

        // Check subtrees to see if they are balanced.
        TreeInfo left = isBalancedTreeHelper(origin.lchild);
        if (!left.balanced) {
            return new TreeInfo(-1, false);
        }
        TreeInfo right = isBalancedTreeHelper(origin.rchild);
        if (!right.balanced) {
            return new TreeInfo(-1, false);
        }
        // Use the height obtained from the recursive calls to
        // determine if the current node is also balanced.
        if (Math.abs(left.height - right.height) < 2) {
            return new TreeInfo(Math.max(left.height, right.height) + 1, true);
        }
        return new TreeInfo(-1, false);
    }

平衡子树暗示了一个事实，每棵子树也是一个子问题。
现在的问题是：按照什么顺序处理这些子问题？

class Solution {
  // Recursively obtain the height of a tree. An empty tree has -1 height
  private int height(TreeNode root) {
    // An empty tree has height -1
    if (root == null) {
      return -1;
    }
    return 1 + Math.max(height(root.left), height(root.right));
  }

  public boolean isBalanced(TreeNode root) {
    // An empty tree satisfies the definition of a balanced tree
    if (root == null) {
      return true;
    }

    // Check if subtrees have height within 1. If they do, check if the
    // subtrees are balanced
    return Math.abs(height(root.left) - height(root.right)) < 2
        && isBalanced(root.left)
        && isBalanced(root.right);
  }
};

// Utility class to store information from recursive calls
final class TreeInfo {
  public final int height;
  public final boolean balanced;

  public TreeInfo(int height, boolean balanced) {
    this.height = height;
    this.balanced = balanced;
  }
}

class Solution {
  // Return whether or not the tree at root is balanced while also storing
  // the tree's height in a reference variable.
  private TreeInfo isBalancedTreeHelper(TreeNode root) {
    // An empty tree is balanced and has height = -1
    if (root == null) {
      return new TreeInfo(-1, true);
    }

    // Check subtrees to see if they are balanced.
    TreeInfo left = isBalancedTreeHelper(root.left);
    if (!left.balanced) {
      return new TreeInfo(-1, false);
    }
    TreeInfo right = isBalancedTreeHelper(root.right);
    if (!right.balanced) {
      return new TreeInfo(-1, false);
    }

    // Use the height obtained from the recursive calls to
    // determine if the current node is also balanced.
    if (Math.abs(left.height - right.height) < 2) {
      return new TreeInfo(Math.max(left.height, right.height) + 1, true);
    }
    return new TreeInfo(-1, false);
  }

  public boolean isBalanced(TreeNode root) {
    return isBalancedTreeHelper(root).balanced;
  }
};

实现一个函数检查一棵树是否平衡。对于这个问题而言， 平衡指的是这棵树任意两个叶子结点到根结点的距离之差不大于1。

/*判断树是否平衡，并不是判断是否是平衡二叉树*/
 
int Max=INT_MIN,Min=INT_MAX,curLen=0;
 
void FindDepth(node* root)
{
	if( root==NULL) 
	{
		return ;
	}
	++curLen;
	FindDepth(root->left);
	if( root->left ==NULL && root->right ==NULL)
	{
		if( curLen > Max )
			Max=curLen;
		else if( curLen < Min )
			Min=curLen;
	}
	FindDepth(root->right);
	--curLen;
}
bool isBalance(node* root)
{
	FindDepth(root);
	return ((Max-Min)<=1);
}