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

1
class Solution {
2
public:
3
    TreeNode* sortedArrayToBST(vector<int>& nums) {
4
        // 主函数：从整个数组区间开始构建
5
        return build(nums, 0, nums.size() - 1);
6
    }
7
private:
8
    TreeNode* build(const vector<int>& nums, int left, int right){
9
        // 递归终止条件：左指针超过右指针
10
        if(left > right) return nullptr;
11

12
        // 找到中间位置，避免 (left + right) / 2 可能带来的溢出风险
13
        int mid = left + (right - left) / 2;
14

15
        // 创建当前子树的根节点
16
        TreeNode* root = new TreeNode(nums[mid]);
17

18
        // 递归地构建左右子树
19
        root->left = build(nums, left, mid - 1);  // 左半部分去盖左楼
20
        root->right = build(nums, mid + 1, right); // 右半部分去盖右楼
21

22
        return root;
23
    }
24
};

1
class Solution {
2
public:
3
    struct Task {
4
        int l, r;
5
        TreeNode** parentPtr;  // 指向父亲节点中 left 或 right 指针的地址
6
        Task(int l_, int r_, TreeNode** p_) : l(l_), r(r_), parentPtr(p_) {}
7
    };
8

9
    TreeNode* sortedArrayToBST(vector<int>& nums) {
10
        if (nums.empty()) return nullptr;
11
        TreeNode* root = nullptr;
12
        stack<Task> st;
13
        st.emplace(0, (int)nums.size() - 1, &root);
14

15
        while (!st.empty()) {
16
            auto [l, r, ptr] = st.top(); st.pop();
17
            if (l > r) { *ptr = nullptr; continue; }
18

19
            int mid = l + (r - l) / 2;
20
            *ptr = new TreeNode(nums[mid]); // 直接给对应的指针赋值
21

22
            // 下一次要处理的任务，先压右后压左
23
            st.emplace(mid + 1, r, &(*ptr)->right);
24
            st.emplace(l, mid - 1, &(*ptr)->left);
25
        }
26
        return root;
27
    }
28
};