LeetCode——将有序数组转换为二叉搜索树

NO.108 将有序数组转换为二叉搜索树 简单

思路一：中序遍历还原 这道题和NO.105和No.106异曲同工，都是通过明确的遍历序列还原二叉树。

例如NO.105，给了前序和中序遍历序列去还原二叉树，前序的作用就是找到根，中序的左右就是找到根的左右子树部分。

本题为什么可以只用一个中序遍历进行还原？其实思路和前两题一样的，根据题目要求(高度平衡二叉树)，中序序列的中间元素作为根，从而也就知道了根的左右子树部分。递归的出口依然是区间没有元素。

public TreeNode sortedArrayToBST(int[] nums) {
    if (nums == null || nums.length == 0) return null;
    return buildBST(nums, 0, nums.length - 1);
}

private TreeNode buildBST(int[] nums, int start, int end) {
    //出口
    if (end < start) {
        return null;
    }
    int mid = (start + end) >>> 1;
    //中间元素作为根
    TreeNode root = new TreeNode(nums[mid]);
    //生成左右子树
    root.left = buildBST(nums, start, mid - 1);
    root.right = buildBST(nums, mid + 1, end);
    return root;
}

时间复杂度：O(n) 每个元素访问一次。

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github