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

Posted by 111qqz on Tuesday, February 21, 2017

TOC

leetcode108

题意:把有一个有序的数组转化成一课高度尽量小的bst(二叉搜索树)

思路:我竟然忘记了什么是bst……..我好傻啊…不过想想可能是因为…最朴素的二叉搜索树几乎用不到…所以很容易忘记吧2333

bst是 binary search tree的缩写..

具体见  维基百科_二叉搜索树

想起来概念就好搞了…直接递归建树即可…类似线段树的build的过程

/* ***********************************************
Author :111qqz
Created Time :2017年02月21日 星期二 13时08分04秒
File Name :108.cpp
************************************************ */
/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    TreeNode* dfs( int l,int r,vector<int>&nums)
    {
        
        int  n = r-l+1;
        if (n<=0) return NULL;
        int  m = n/2;
        cout<<"l:"<<l<<" r:"<<r<<endl;
        TreeNode* rt = new TreeNode(nums[l+m]);
        rt->left = dfs(l,l+m-1,nums);
        rt->right = dfs(l+m+1,r,nums);
        return rt;
    }
        
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {

        int siz = nums.size();
        if (siz==0) return NULL;
         return dfs(0,siz-1,nums);
    }

};