【108-Convert Sorted Array to Binary Search Tree（排序数组转变为平衡二叉树）】

【LeetCode-面试算法经典-Java实现】【所有题目目录索引】

原题

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

题目大意

　　给定一个升序排列的二叉树，将其转换为一棵高度平衡的二叉树。

解题思路

　　采用递归分治法。

代码实现

树结点类

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

算法实现类

public class Solution {

    public TreeNode sortedArrayToBST(int[] nums) {
        // 参数检验
        if (nums == null || nums.length < 1) {
            return null;
        }

        // 递归分治法求解
        return solve(nums, 0, nums.length - 1);
    }

    /**
     * 递归分治求解方法
     *
     * @param nums  升序排序数组
     * @param start 开始位置
     * @param end   结束位置
     * @return 根结点
     */
    public TreeNode solve(int[] nums, int start, int end) {
        // 还有未处理的数据
        if (start <= end) {
            // 找蹭位置
            int mid = start + ((end - start) >> 1);
            // 构造根结点
            TreeNode root = new TreeNode(nums[mid]);
            // 求左子树
            root.left = solve(nums, start, mid - 1);
            // 求右子树
            root.right = solve(nums, mid + 1, end);
            // 返回结果
            return root;
        }

        return null;
    }
}

评测结果

　　点击图片，鼠标不释放，拖动一段位置，释放后在新的窗口中查看完整图片。

特别说明

欢迎转载，转载请注明出处【http://blog.****.net/derrantcm/article/details/47392999】