首页 > 代码库 > 108. Convert Sorted Array to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree

题目:

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

题目只有一句话:把一个按升序排列的数组,装换成一个平衡二叉树。

代码:

很久没研究数据结构了,先百度一下平衡二叉树的概念,总结如下:

  1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  3. 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树

要满足一下条件,对于没有排序的数组来说,就比较麻烦,但对于已排序的数组,大都用二分递归转换方法来处理

算法逻辑很简单,就是先找到中间元素,创建根节点,左右子树分别用中间元素左边(即小于中间节点的元素)和中间元素右边(即大于中间节点的元素)递归创建。

这样,节点的左子树永远比节点小,右子树永远比节点大,且由于平均递归创建每一层的子树,所以两个子树的高度差不会超过1。

java代码:

    //将已排序数组变成平衡二叉树
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode node = creatTreeNode(nums,0,nums.length-1);        
         return node;
    }
    //递归创建子树,大小为剩余元素中间节点
    public TreeNode creatTreeNode(int[] nums,int left,int right) {
        if(left>right) {
            return null;
        }       
        int mid = (left+right)/2;
        TreeNode node = new TreeNode(nums[mid]);
        
        node.left = creatTreeNode(nums, left, mid - 1);
        node.right = creatTreeNode(nums, mid+1, right);
        return node;
    }

亲测确实可以:

技术分享

108. Convert Sorted Array to Binary Search Tree