时间轴

2025-12-01

init

题目：

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

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-interview-150

分治思想：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <vector>
using std::vector;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode()
		: val(0)
		, left(nullptr)
		, right(nullptr)
	{
	}
	TreeNode(int x)
		: val(x)
		, left(nullptr)
		, right(nullptr)
	{
	}
	TreeNode(int x, TreeNode *left, TreeNode *right)
		: val(x)
		, left(left)
		, right(right)
	{
	}
};

class Solution {
    private:
	TreeNode *buildBST(vector<int> &nums, int begin, int end)
	{
		if (end < begin) {
			return NULL;
		}
		// 中序遍历结果为单调递增序列
		TreeNode *root = new TreeNode;
		int middle = (begin + end) / 2;
		root->val = nums[middle];
		root->left = buildBST(nums, begin, middle - 1);
		root->right = buildBST(nums, middle + 1, end);
		return root;
	}

    public:
	TreeNode *sortedArrayToBST(vector<int> &nums)
	{
		return buildBST(nums, 0, nums.size() - 1);
	}
};