108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

將一個按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹。

本題中，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點(diǎn) 的左右兩個子樹的高度差的絕對值不超過 1。

例如:

給定有序數(shù)組: [-10,-3,0,5,9],

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

      0
     / \
   -3   9
   /   /
 -10  5

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

• 創(chuàng)建二叉搜索樹

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

• 1. 遞歸法

思路：由于要求是平衡二叉搜索樹，所以可以采用類似線段樹的創(chuàng)建過程LeetCode 307. 區(qū)域和檢索 - 數(shù)組可修改 - 簡書

平衡二叉樹：通俗的說，就是二叉樹的最大最小深度不超過1

1. 取出數(shù)組的中間節(jié)點(diǎn)作為根節(jié)點(diǎn)，左邊的元素為左子樹，右邊的元素作為右子樹
2. 遞歸調(diào)用創(chuàng)建即可

注意：為防止當(dāng)數(shù)組很大時，使用（l + r）/ 2 求中間位置可能會溢出

    public TreeNode sortedArrayToBST(int[] nums) {
        return nums == null ? null : buildTree(nums, 0, nums.length);
    }

    private TreeNode buildTree(int[] nums, int l, int r) {
        if (l > r) return null;
        int mid = l + (r - l) / 2;
        TreeNode cur = new TreeNode(nums[mid]);
        cur.left = buildTree(nums, l, mid - 1);
        cur.right = buildTree(nums, mid + 1, r);
        return cur;
    }

復(fù)雜度分析：

• 時間復(fù)雜度：O(n), 需要遍歷每個元素添加到二叉樹中
• 空間復(fù)雜度：O(n)

• 源碼

• 我會每天更新新的算法，并盡可能嘗試不同解法，如果發(fā)現(xiàn)問題請指正

• Github