题解 | #升序数组转平衡二叉树,通用解法O(n^2)#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param num int整型一维数组 
     * @return TreeNode类
     */
    public TreeNode sortedArrayToBST (int[] num) {
        if(num == null || num.length == 0) return null ;
        TreeNode root = new TreeNode(num[0]) ;
        for(int i = 1 ; i < num.length ; i ++) {
            insert(root , num[i]) ;
            root = rotate(root) ;
        }
        return root ;
    }
    public void insert(TreeNode root , int val) {
        if(root == null) return ;
        if(root.left == null && val < root.val) root.left = new TreeNode(val) ;
        if(root.right == null && val > root.val) root.right = new TreeNode(val) ;
        if(val < root.val) {
            insert(root.left , val) ;        
        } else if(val > root.val) {
            insert(root.right , val) ;
        }
    }
    public TreeNode rotate(TreeNode root) {
        if(height(root.left) - height(root.right) > 1) {
            return rightRotate(root) ;
        } else if(height(root.left) - height(root.right) < 1) {
            return leftRotate(root) ;
        }
        return root ;
    }
    public TreeNode leftRotate(TreeNode root) {
        if(root == null) return null ;
        if(height(root.right.left) - height(root.right.right) > 1) {
            root.right = rightRotate(root.right) ;
        }
        TreeNode n1 = root ;
        TreeNode n2 = root.right ;
        n1.right = n2.left ;
        n2.left = n1 ;
        return n2 ;
        
    }
    public TreeNode rightRotate(TreeNode root) {
        if(root == null) return null;
        if(height(root.left.right) - height(root.left.left) > 1) {
            root.left = leftRotate(root.left) ;
        }
        TreeNode n1 = root ;
        TreeNode n2 = root.left ;
        n1.left = n2.right ;
        n2.right = n1 ;
        return n2 ;
    }
    public int height(TreeNode root) {
        if(root == null) return 0 ;
        int l = height(root.left) ;
        int r = height(root.right) ;
        return  l > r ? l + 1 : r + 1 ; 
    }    
}