Convert Sorted Array to Binary Search Tree (LeetCode)---递归建立二叉搜索树
description:
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
code:Hint:类似于二分搜索,找到中点值作为根,再递归地建立左右子树
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: TreeNode *sortedArrayToBST(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function if(num.size() == 0) { return NULL; } return sorted2bst(num,0,num.size()-1); } TreeNode *sorted2bst(vector<int> &num, int st, int end) { if(st<=end) { int mid = (st+end)>>1; TreeNode *root = new TreeNode(num[mid]); root->left = sorted2bst(num,st,mid-1); root->right = sorted2bst(num,mid+1,end); return root; } else return NULL; }};