秋高斋

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

发表于 更新于 分类于
本文字数： 489 阅读时长 ≈ 1 分钟
经典的中序遍历

leetcode-108. 将有序数组转换为二叉搜索树

经典的递归中序遍历树，常做常新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

    TreeNode* helper(vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }
};