二叉搜索树与二叉平衡搜索树

二叉平衡搜索树是一种特殊的二叉搜索树，其保持一定的平衡关系，要求每一个节点的左右子树的高度不会相差超过1

1.下面是一到二叉平衡搜索树的题，leetcode108

题目描述：

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解决思路：

思路一
按照AVL树的正常处理代码，写出AVL树中的insert、balance等方法，实现将任意顺序的数值插入此树均可以，
上边思路太繁琐，AVL树的实现需要很多代码，而且由于这种实现的AVL树具有对任意数据的输入能力，因此自然其运行较慢，没有利用此题目中的有序升序数组的特性。
思路二
中序遍历
本题给出的数值是以一个按照升序排列的有序数组，因此应该利用升序的特点
二叉搜索平衡树，中间节点的值大于左子树中节点的值，小于右子树中节点的值
因此每次讲数组中中间位置的数值插入中间节点，
左半块的中间位置的数值插入左子节点，右半块的中间位置的数值插入右子节点

代码：

思路一的代码，太繁琐，执行速度太慢，但是这种思路需要掌握，这是比较完整的常用二叉平衡搜索树的写法，对任意数据都有处理能力：

class Solution {
    //思路一
    //按照AVL树的正常处理代码，写出AVL树中的insert、balance等方法，实现将任意顺序的数值插入此树均可以
    //上边思路太繁琐，AVL树的实现需要很多代码
    //思路二
    //中序遍历
    //本题给出的数值是以一个按照升序排列的有序数组，因此应该利用升序的特点
    //二叉搜索平衡树，中间节点的值大于左子树中节点的值，小于右子树中节点的值
    //因此每次讲数组中中间位置的数值插入中间节点，
    //左半块的中间位置的数值插入左子节点，右半块的中间位置的数值插入右子节点
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = null;
        for(int x : nums){
            root = insert(x, root);
        }
        
        return root;
    }
    private TreeNode insert(int x, TreeNode root){
        if(root == null){
            return new TreeNode(x);
        }
        int compareResult = x - root.val;
        if(compareResult < 0){
            root.left = insert(x, root.left);
        }
        else if(compareResult > 0){
            root.right = insert(x, root.right);
        }
        
        return balance(root);
    }
    private int height(TreeNode root){
        if(root == null){
            return -1;
        }
        return Math.max(height(root.left), height(root.right)) + 1;
    }
    private TreeNode balance(TreeNode root){
        if(root == null){
            return root;
        }
        if(height(root.left) - height(root.right) > 1){
            if(height(root.left.left) >= height(root.left.right)){
                root = leftChildOne(root);
            }
            else{
                root = leftChildTwo(root);
            }
        }
        else if(height(root.right) - height(root.left) > 1){
            if(height(root.right.right) >= height(root.right.left)){
                root = rightChildOne(root);
            }
            else{
                root = rightChildTwo(root);
            }
        }
        else{;}
        
        return root;
    }
    
    private TreeNode leftChildOne(TreeNode k2){
        TreeNode k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        
        return k1;
    }
    private TreeNode leftChildTwo(TreeNode k3){
        k3.left = rightChildOne(k3.left);
        
        return leftChildOne(k3);
    }
    private TreeNode rightChildOne(TreeNode k2){
        TreeNode k1 = k2.right;
        k2.right = k1.left;
        k1.left = k2;
        
        return k1;
    }
    private TreeNode rightChildTwo(TreeNode k3){
        k3.right = leftChildOne(k3.right);
        
        return rightChildOne(k3);
    }
}

思路二的代码，针对此题目输入数据的特点，代码量小，运行快：

class Solution {
    //思路一
    //按照AVL树的正常处理代码，写出AVL树中的insert、balance等方法，实现将任意顺序的数值插入此树均可以
    //上边思路太繁琐，AVL树的实现需要很多代码
    //思路二
    //中序遍历
    //本题给出的数值是以一个按照升序排列的有序数组，因此应该利用升序的特点
    //二叉搜索平衡树，中间节点的值大于左子树中节点的值，小于右子树中节点的值
    //因此每次讲数组中中间位置的数值插入中间节点，
    //左半块的中间位置的数值插入左子节点，右半块的中间位置的数值插入右子节点
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null){
            return null;
        }
        
        return insert(nums, 0, nums.length-1);
    }
    private TreeNode insert(int[] nums, int lo, int hi){
        if(lo > hi){
            return null;
        }
        
        int mid = lo + (hi - lo)/2;
        TreeNode root = new TreeNode(nums[mid]);
        
        root.left = insert(nums, lo, mid-1);
        root.right = insert(nums, mid + 1, hi);
        
        return root;
    }
}