leetcode 108. Convert Sorted Array to Binary Search Tree（有序数组转化成bst）

2017-02-21 · 1 min read · binary search tree

题意：把有一个有序的数组转化成一课高度尽量小的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};