> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/convert-sorted-array-to-binary-search-tree.md).

# Convert Sorted Array to Binary Search Tree

<https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/>

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

## Thoughts

平衡二叉搜索树也就是把中点作为root，左右分别对应左右子树。\
因此利用树的递归定义，把原问题分成左右两个相同的子问题, 再把它们用中点合并起来即可。

## Code

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode helper(int start, int end, int[] nums) {
        if (start > end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = helper(start, mid - 1, nums);
        node.right = helper(mid + 1, end, nums);

        return node;
    }


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

        return helper(0, nums.length - 1, nums);
    }
}
```

## Analysis

数组每个节点访问一遍，因此时间复杂度为O(n)

## Ver.2

用另一个 stack记录每个节点对应的range, 并且让结点先创建出来给left和right再修改值. 这样就不用费心去找left和right到底在哪了。

```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        const int N = nums.size();
        if (N == 0) return NULL;
        stack<TreeNode*> s;
        stack<pair<int, int>> ranges;
        const auto root = new TreeNode(nums[(N - 1) / 2]);
        s.push(root);
        ranges.push({0, N - 1});
        while (!s.empty()) {
            auto cur = s.top();
            const auto range = ranges.top();
            s.pop();
            ranges.pop();
            const int c_mid = range.first + (range.second - range.first) / 2; 
            cur->val = nums[c_mid];
            if (range.first != c_mid) {
                ranges.push({range.first, c_mid - 1});
                const auto l = new TreeNode(-1);
                cur->left = l;
                s.push(l);
            } 
            if (range.second != c_mid) {
                ranges.push({c_mid + 1, range.second});
                const auto r = new TreeNode(-1);
                cur->right = r;
                s.push(r);
            }
        }
        return root;
    }
};
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/convert-sorted-array-to-binary-search-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.