Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：把一个有序的数组转化成一棵高度尽量小的bst(二叉搜索树)
思路：我竟然忘记了什么是bst……..我好傻啊…不过想想可能是因为…最朴素的二叉搜索树几乎用不到…所以很容易忘记吧2333
bst是 binary search tree的缩写..
具体见 维基百科_二叉搜索树
想起来概念就好搞了…直接递归建树即可…类似线段树的build的过程
1/* ***********************************************
2Author :111qqz
3Created Time :2017年02月21日 星期二 13时08分04秒
4File Name :108.cpp
5************************************************ */
6/**
7
8 * Definition for a binary tree node.
9
10 * struct TreeNode {
11
12 * int val;
13
14 * TreeNode *left;
15
16 * TreeNode *right;
17
18 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
19
20 * };
21
22 */
23
24class Solution {
25
26public:
27
28 TreeNode* dfs( int l,int r,vector<int>&nums)
29 {
30
31 int n = r-l+1;
32 if (n<=0) return NULL;
33 int m = n/2;
34 cout<<"l:"<<l<<" r:"<<r<<endl;
35 TreeNode* rt = new TreeNode(nums[l+m]);
36 rt->left = dfs(l,l+m-1,nums);
37 rt->right = dfs(l+m+1,r,nums);
38 return rt;
39 }
40
41
42 TreeNode* sortedArrayToBST(vector<int>& nums) {
43
44 int siz = nums.size();
45 if (siz==0) return NULL;
46 return dfs(0,siz-1,nums);
47 }
48
49};